Advertisement
he_obviously

Untitled

Dec 19th, 2021 (edited)
891
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.19 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <set>
  6. #include <map>
  7.  
  8. using namespace std;
  9.  
  10. const long long MOD = 1442501923, MOD2 = 2556975823;
  11. const long long p = 1337057, p2 = 1216091;
  12.  
  13. int main() {
  14.     int n, m;
  15.     cin >> n >> m;
  16.     vector<vector<int>> g(n + 1), gg(n + 1);
  17.     for (int i = 0; i < m; ++i) {
  18.         int v, u;
  19.         cin >> v >> u;
  20.         g[v].push_back(u);
  21.         gg[v].push_back(u);
  22.         g[u].push_back(v);
  23.         gg[u].push_back(v);
  24.     }
  25.     for (int i = 1; i <= n; ++i) {
  26.         gg[i].push_back(i);
  27.         sort(g[i].begin(), g[i].end());
  28.         sort(gg[i].begin(), gg[i].end());
  29.     }
  30.     vector<long long> h, hh, h2, hh2;
  31.     for (int i = 1; i <= n; ++i) {
  32.         long long hs = 0LL, hs2 = 0LL;
  33.         long long pow = 1LL, pow2 = 1LL;
  34.         for (int j: g[i]) {
  35.             hs = (hs + (long long)(j) * pow) % MOD;
  36.             hs2 = (hs2 + (long long)(j) * pow2) % MOD2;
  37.             pow = (pow * p) % MOD;
  38.             pow2 = (pow2 * p2) % MOD2;
  39.         }
  40.         h.push_back(hs);
  41.         h2.push_back(hs2);
  42.         hs = 0LL;
  43.         pow = 1LL;
  44.         hs2 = 0LL;
  45.         pow2 = 1LL;
  46.         for (int j: gg[i]) {
  47.             hs = (hs + (long long)(j) * pow) % MOD;
  48.             hs2 = (hs2 + (long long)(j) * pow2) % MOD2;
  49.             pow = (pow * p) % MOD;
  50.             pow2 = (pow2 * p2) % MOD2;
  51.         }
  52.         hh.push_back(hs);
  53.         hh2.push_back(hs2);
  54.     }
  55.     sort(h.begin(), h.end());
  56.     sort(hh.begin(), hh.end());
  57.     sort(h2.begin(), h2.end());
  58.     sort(hh2.begin(), hh2.end());
  59.     h.push_back(-1);
  60.     hh.push_back(-1);
  61.     h2.push_back(-1);
  62.     hh2.push_back(-1);
  63.     long long ans = 0LL;
  64.     int prev = 0;
  65.     for (int i = 1; i < n + 1; ++i) {
  66.         if (h[i] != h[prev] || h2[i] != h2[prev]) {
  67.             ans += (long long)(i - prev) * (long long)(i - prev - 1) / 2LL;
  68.             prev = i;
  69.         }
  70.     }
  71.     prev = 0;
  72.     for (int i = 1; i < n + 1; ++i) {
  73.         if (hh[i] != hh[prev] || hh2[i] != hh2[prev]) {
  74.             ans += (long long)(i - prev) * (long long)(i - prev - 1) / 2LL;
  75.             prev = i;
  76.         }
  77.     }
  78.     cout << ans;
  79.     return 0;
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement