fork download
  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
stdin
Standard input is empty
stdout
0