ohwhatalovelyday

Untitled

Jan 30th, 2021
141
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.61 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define FASTER() ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  4. #define ff first
  5. #define ss second
  6. #define pb push_back
  7. #define all(a) a.begin(), a.end()
  8. #define dbg(x) cerr<<" "<<#x<<" "<<x<<endl
  9.  
  10. typedef long long ll;
  11.  
  12. using namespace std;
  13.  
  14. const int inf = 1e8 + 7;
  15. const int maxn = 3e5 + 13;
  16. vector <int> gr[maxn];
  17.  
  18. struct edge {
  19.     int u, cnt, idx;
  20. };
  21.  
  22. bool cmp (const edge &a, const edge &b) {
  23.     return a.cnt < b.cnt;
  24. }
  25.  
  26. int main() {
  27.     FASTER();
  28.     int n, m;
  29.     cin >> n >> m;
  30.     vector <int> order(n, inf);
  31.     vector <edge> vertexes(n, {inf, inf});
  32.     for(int i = 0; i < m; i++) {
  33.         int u, v;
  34.         cin >> u >> v;
  35.         u--; v--;
  36.         gr[u].pb(v);
  37.         vertexes[u].u = u;
  38.         vertexes[u].cnt++;
  39.         gr[v].pb(u);
  40.         vertexes[v].u = v;
  41.         vertexes[v].cnt++;
  42.     }
  43.    
  44.     sort(all(vertexes), cmp);
  45.     for(int i = 0; i < n; i++) {
  46.         if(vertexes[i].u == inf) {
  47.             continue;
  48.         }
  49.         order[vertexes[i].u] = i;
  50.     }
  51.     vector <int> c(n, 0);
  52.     int ans = 0;
  53.     for(auto a : vertexes) {
  54.         int i = a.u;
  55.         if(i == inf) {
  56.             continue;
  57.         }
  58.         for(int j : gr[i]) {
  59.             c[j]++;
  60.         }
  61.         for(auto j : gr[i]) {
  62.             if(order[j] > order[i]) {
  63.                 for (auto k : gr[j]) {
  64.                     if(order[k] > order[j]) {
  65.                         ans += c[k];
  66.                     }
  67.                 }
  68.             }
  69.         }
  70.         for(int j : gr[i]) {
  71.             c[j]--;
  72.         }
  73.     }
  74.     cout << ans;
  75. }
Advertisement
Add Comment
Please, Sign In to add comment