fork download
copy 
  1. #include "iostream"
  2. #include "algorithm"
  3. #include "vector"
  4. #include "set"
  5. #include "map"
  6. #include "cstring"
  7. #include "string"
  8. #include "vector"
  9. #include "cassert"
  10. #include "queue"
  11. #include "cstdio"
  12. #include "cstdlib"
  13. #include "ctime"
  14. #include "cmath"
  15. #include "bitset"
  16. #include "unordered_map"
  17.  
  18. using namespace std;
  19.  
  20. typedef long long ll;
  21. typedef pair < int, int > ii;
  22.  
  23. const int N = 50000 + 5;
  24. const int K = 200;
  25.  
  26. int n, m;
  27. bool h[N];
  28. vector < int > v[N];
  29. unordered_map < int, int > M[N];
  30.  
  31. int main () {
  32.  
  33.     scanf("%d %d", &n, &m);
  34.  
  35.     for(int i = 1; i <= m; i++) {
  36.         int x, y;
  37.         scanf("%d %d", &x, &y);
  38.         v[x].push_back(y);
  39.         v[y].push_back(x);
  40.     }
  41.  
  42.     ll ans = 0;
  43.  
  44.     for(int i = 1; i <= n; i++)
  45.         if(v[i].size() <= K)
  46.             for(auto x : v[i])
  47.                 for(auto y : v[i])
  48.                     if(x < y)
  49.                         ans += M[x][y]++;
  50.  
  51.     for(int i = 1; i <= n; i++) {
  52.         if(v[i].size() > K) {
  53.             for(auto x : v[i])
  54.                 h[x] = 1;
  55.             for(int j = 1; j <= n; j++) {
  56.                 if(j != i and (v[j].size() <= K or j < i)) {
  57.                     int cnt = 0;
  58.                     for(auto y : v[j])
  59.                         if(y != i and h[y])
  60.                             ans += cnt++;
  61.                 }
  62.             }
  63.             for(auto x : v[i])
  64.                 h[x] = 0;
  65.         }
  66.     }
  67.  
  68.     printf("%lld\n", ans / 2);
  69.  
  70.     return 0;
  71.  
  72. }
Success #stdin #stdout 0s 5464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/62nybh
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!