fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //
  4. const int mx = 1e5 + 5;
  5. const int S = 320;
  6. //
  7. struct hash_pair
  8. {
  9.     template <class T1, class T2>
  10.     size_t operator () (const pair<T1, T2> &p) const
  11.     {
  12.         size_t hash1 = hash<T1>{}(p.first);
  13.         size_t hash2 = hash<T2>{}(p.second);
  14.         //
  15.         return hash1 ^ (hash2 + 0x9e3779b9 + (hash1 << 6) + (hash1 >> 2));
  16.     }
  17. };
  18. //
  19. namespace real
  20. {
  21.     int cnt, lab[mx];
  22.     //
  23.     void reset (int n)
  24.     {
  25.         cnt = n;
  26.         memset(lab, -1, sizeof lab);
  27.     }
  28.     int find_set (int v)
  29.     {
  30.         return lab[v] < 0 ? v : lab[v] = find_set(lab[v]);
  31.     }
  32.     void union_sets (int u, int v)
  33.     {
  34.         u = find_set(u);
  35.         v = find_set(v);
  36.         if (u == v)
  37.             return;
  38.         --cnt;
  39.         if (lab[u] > lab[v])
  40.             swap(u, v);
  41.         lab[u] += lab[v];
  42.         lab[v] = u;
  43.     }
  44. }
  45. namespace vir
  46. {
  47.     int n, cnt, lab[mx];
  48.     unordered_map<int, int> mp;
  49.     //
  50.     void reset (void)
  51.     {
  52.         mp.clear();
  53.         fill(lab + 1, lab + cnt + 1, 0);
  54.         n = cnt = 0;
  55.     }
  56.     void make_set (int u)
  57.     {
  58.         ++n, ++cnt;
  59.         mp[u] = n;
  60.         lab[n] = -1;
  61.     }
  62.     int find_set (int v)
  63.     {
  64.         return lab[v] < 0 ? v : lab[v] = find_set(lab[v]);
  65.     }
  66.     void union_sets (int u, int v)
  67.     {
  68.         if (mp.find(u) == mp.end())
  69.             make_set(u);
  70.         u = find_set(mp[u]);
  71.         if (mp.find(v) == mp.end())
  72.             make_set(v);
  73.         v = find_set(mp[v]);
  74.         if (u == v)
  75.             return;
  76.         --cnt;
  77.         if (lab[u] > lab[v])
  78.             swap(u, v);
  79.         lab[u] += lab[v];
  80.         lab[v] = u;
  81.     }
  82. }
  83. //
  84. void process (void)
  85. {
  86.     int n, m, k;
  87.     int a, b, lim, t[mx];
  88.     pair<int, int> p[mx];
  89.     unordered_set<pair<int, int>, hash_pair> edge, temp, delete_set;
  90.     //
  91.     cin >> n >> m >> k;
  92.     for (int i = 0; i < m; ++i)
  93.     {
  94.         cin >> a >> b;
  95.         if (a > b)
  96.             swap(a, b);
  97.         edge.insert(make_pair(a, b));
  98.     }
  99.     for (int i = 0; i < k; ++i)
  100.     {
  101.         cin >> t[i] >> a >> b;
  102.         if (a > b)
  103.             swap(a, b);
  104.         p[i] = make_pair(a, b);
  105.     }
  106.  
  107.     real::reset(n);
  108.     for (auto it : edge)
  109.         real::union_sets(it.first, it.second);
  110.     cout << real::cnt;
  111.  
  112.     for (int i = 0; i * S < k; ++i)
  113.     {
  114.         lim = min(k, (i + 1) * S);
  115.  
  116.         delete_set.clear();
  117.         for (int j = i * S; j < lim; ++j)
  118.             if (t[j] == 2)
  119.                 delete_set.insert(p[j]);
  120.  
  121.         real::reset(n);
  122.         temp.clear();
  123.         for (auto it : edge)
  124.             if (delete_set.find(it) == delete_set.end())
  125.                 real::union_sets(it.first, it.second);
  126.             else
  127.                 temp.insert(it);
  128.  
  129.         for (int j = i * S; j < lim; ++j)
  130.         {
  131.             if (t[j] == 1)
  132.                 edge.insert(p[j]);
  133.             else
  134.                 edge.erase(p[j]),
  135.                 temp.erase(p[j]);
  136.  
  137.             vir::reset();
  138.             for (auto it : temp)
  139.                 vir::union_sets(real::find_set(it.first), real::find_set(it.second));
  140.             for (int d = i * S; d <= j; ++d)
  141.                 if (t[d] != 2 && edge.find(p[d]) != edge.end())
  142.                     vir::union_sets(real::find_set(p[d].first), real::find_set(p[d].second));
  143.  
  144.             cout << ' ' << real::cnt - (vir::n - vir::cnt);
  145.         }
  146.     }
  147. }
  148. //
  149. signed main (void)
  150. {
  151.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  152.     process();
  153. }
  154.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/e1lNb1
https://o...content-available-to-author-only...i.info/problem/sqrt2_a
language:
C++14 (gcc 8.3)
created:
7 hours 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!