cosenza987

Untitled

Nov 28th, 2021
719
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Problem: D. Social Network
  2. // Contest: Codeforces - Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2)
  3. // Memory Limit: 256 MB
  4. // Time Limit: 2000 ms
  5. // Date / Time: 2021-11-28 17:36:41
  6. // Author: cosenza
  7. // всё что ни делается - всё к лучшему
  8. // check list -> long long, special cases, array size, mod (a*b%p*c%p not a*b*c%p  ,  (a-b+p)%p not a-b )
  9. //
  10. // Powered by CP Editor (https://cpeditor.org)
  11.  
  12. //#pragma GCC optimize("Ofast")
  13. //#pragma GCC optimize ("unroll-loops")
  14. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  15. //THESE ARE LAST DITCH EFFORTS!!!
  16.  
  17. #include <bits/stdc++.h>
  18.  
  19. using namespace std;
  20.  
  21. struct DSU {
  22.     int getSize(int x) { return -par[getPar(x)]; }
  23.     int getPar(int x) {
  24.         while(par[x] >= 0) {
  25.             x = par[x];
  26.         }
  27.         return x;
  28.     }
  29.  
  30.     bool makeUnion(int a, int b) {
  31.         a = getPar(a), b = getPar(b);
  32.         if(a == b) return false;
  33.         if(par[a] > par[b]) std::swap(a, b);
  34.         op.emplace_back(a, par[a]);
  35.         op.emplace_back(b, par[b]);
  36.         par[a] += par[b];
  37.         par[b] = a;
  38.         return true;
  39.     }
  40.  
  41.     void init(int n) {
  42.         par.resize(n);
  43.         for(int i = 0; i < n; i++) {
  44.             par[i] = -1;
  45.         }
  46.         op.clear();
  47.     }
  48.  
  49.     void rollBack() {
  50.         par[op.back().first] = op.back().second;
  51.         op.pop_back();
  52.     }
  53.  
  54.     std::vector<int> par;
  55.     std::vector<std::pair<int, int>> op;
  56. };
  57.  
  58. int main() {
  59.     ios_base::sync_with_stdio(false);
  60.     cin.tie(0);
  61.     int n, d;
  62.     cin >> n >> d;
  63.     DSU dsu;
  64.     dsu.init(n);
  65.     int k = 1;
  66.     while(d--) {
  67.         int x, y;
  68.         vector<int> s;
  69.         cin >> x >> y;
  70.         x--; y--;
  71.         if(!dsu.makeUnion(x, y)) {
  72.             k++;
  73.         }
  74.         for(int i = 0; i < n; i++) {
  75.             if(dsu.getPar(i) == i) {
  76.                 s.push_back(dsu.getSize(i));
  77.             }
  78.         }
  79.         sort(s.begin(), s.end(), std::greater<int>());
  80.         int ans = 0;
  81.         for(int i = 0; i < k and i < s.size(); i++) {
  82.             ans += s[i];
  83.         }
  84.         cout << --ans << "\n";
  85.     }
  86.     return 0;
  87. }
RAW Paste Data