Advertisement
Guest User

Untitled

a guest
Dec 16th, 2018
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.39 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <map>
  6. #include <stack>
  7. #include <cmath>
  8. #include <set>
  9. #include <utility>
  10. #include <iomanip>
  11. #include <cstdlib>
  12. #include <ctime>
  13. #include <list>
  14. #include <numeric>
  15. #include <unordered_map>
  16. using namespace std;
  17.  
  18. int main() {
  19. freopen("input.txt", "r", stdin);
  20. //freopen("e.out", "w", stdout);
  21. int n, k;
  22. cin >> n >> k;
  23. long long a, b;
  24. vector<long long> vv(n+1);
  25. vector<long long> vv1(n+1);
  26. long long t = 941;
  27. long long t1 = 757;
  28. vector<long long> tt(n+1);
  29. vector<long long> tt1(n+1);
  30. long long m = 1817814218137;
  31. long long m1 = 8132721212411;
  32. tt[0]=1;
  33. tt1[0]=1;
  34. for (int i = 0; i < n; ++i) {
  35.     tt[i+1]=(tt[i]*t)%m;
  36.     tt1[i+1]=(tt1[i]*t1)%m1;
  37. }
  38. for (long long i = 0 ; i < k; ++i) {
  39.     scanf("%lld%lld", &a, &b);
  40.  
  41.     vv[a]+=(b*tt[b])%m;
  42.     vv[a]%=m;
  43.     vv[b]+=(a*tt[a])%m;
  44.     vv[b]%=m;
  45.     vv1[a]+=(b*tt1[b])%m1;
  46.     vv1[a]%=m1;
  47.     vv1[b]+=(a*tt1[a])%m1;
  48.     vv1[b]%=m1;
  49.  
  50.  
  51. }
  52. unordered_map<long long, int> mm;
  53. unordered_map<long long, int> mm1;
  54. long long ans = 0;
  55. for (long long i = 1; i <= n; ++i) {
  56.         mm[(vv[i]+(i*tt[i])%m)%m]++;
  57.         mm1[(vv1[i]+(i*tt1[i])%m1)%m1]++;
  58.         ans+=min(mm[(vv[i]+(i*tt[i])%m)%m], mm1[(vv1[i]+(i*tt1[i])%m1)%m1])-1;
  59.         mm[vv[i]]++;
  60.         mm1[vv1[i]]++;
  61.         ans+=min(mm[vv[i]], mm1[vv1[i]])-1;
  62. }
  63. cout << ans << "\n";
  64. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement