fork(10) download
copy 
  1. #include <cstdio>
  2. #include <cassert>
  3. #include <cstring>
  4. #include <map>
  5.  
  6. using namespace std;
  7.  
  8. #define forn(i, n) for (int i = 0; i < (int)(n); i++)
  9. #define mp make_pair
  10.  
  11. typedef pair <int, int> pii;
  12.  
  13. const int maxn = (int)3e5 + 10;
  14. const int max_mem = maxn * 10;
  15.  
  16. int n, k, a[maxn], b[maxn], pa[maxn];
  17. int p[maxn], size[maxn];
  18. char type[maxn];
  19. map <pii, int> ind;
  20. int mpos, mem[maxn * 4];
  21. int cc, u[maxn];
  22. int sn, ss[max_mem];
  23.  
  24. inline int Set( int *x, int y )
  25. {
  26.   assert(sn < max_mem);
  27.   ss[sn++] = (int)x, ss[sn++] = *x;
  28.   return *x = y;
  29. }
  30.  
  31. inline void Restore( int old )
  32. {
  33.   while (sn > old)
  34.     sn -= 2, *((int *)(ss[sn])) = ss[sn + 1];
  35. }
  36.  
  37. int Get( int a )
  38. {
  39.   return a == p[a] ? a : Set(&p[a], Get(p[a]));
  40. }
  41.  
  42. void Join( int a, int b )
  43. {
  44.   if (size[a] > size[b])
  45.     swap(a, b);
  46.   Set(&p[a], b);
  47.   Set(&size[b], size[b] + size[a]);
  48. }
  49.  
  50. void Do( int L, int R, int pn, int *p, int ans )
  51. {
  52.   int oldMPos = mpos, oldSN = sn;
  53.   int e, x, y, pn1 = 0, *p1 = mem + mpos;
  54.  
  55.   cc++;
  56.   for (int i = L; i < R; i++)
  57.     if (type[i] == '-')
  58.       u[pa[i]] = cc;
  59.   forn(i, pn)
  60.     if (u[e = p[i]] == cc)
  61.     {
  62.       assert(mpos < maxn * 4);
  63.       p1[pn1++] = e, mpos++;
  64.     }
  65.     else if (pa[e] > L && (x = Get(a[e])) != (y = Get(b[e])))
  66.       Join(x, y), ans--;
  67.  
  68.   if (R - L == 1)
  69.   {
  70.     if (type[L] == '?')
  71.       printf("%d\n", ans);
  72.   }
  73.   else
  74.   {
  75.     int M = (L + R) / 2;
  76.     Do(L, M, pn1, p1, ans);
  77.     for (int i = L; i < M; i++)
  78.       if (type[i] == '+')
  79.       {
  80.         assert(mpos < maxn * 4);
  81.         p1[pn1++] = i, mpos++;
  82.       }
  83.     Do(M, R, pn1, p1, ans);
  84.   }
  85.   mpos = oldMPos, Restore(oldSN);
  86. }
  87.  
  88. int main()
  89. {
  90.   freopen("connect.in", "r", stdin);
  91.   freopen("connect.out", "w", stdout);
  92.  
  93.   scanf("%d%d", &n, &k);
  94.   forn(i, k)
  95.   {
  96.     pa[i] = k;
  97.     scanf(" %c", &type[i]);
  98.     if (type[i] != '?')
  99.     {
  100.       scanf("%d%d", &a[i], &b[i]), a[i]--, b[i]--;
  101.       if (a[i] > b[i])
  102.         swap(a[i], b[i]);
  103.     }
  104.  
  105.     pii p = mp(a[i], b[i]);
  106.     if (ind.count(p))
  107.       pa[i] = ind[p], pa[pa[i]] = i, ind.erase(p);
  108.     else
  109.       ind[p] = i;
  110.   }
  111.   forn(i, n)
  112.     p[i] = i, size[i] = 1;
  113.  
  114.   if (k)
  115.     Do(0, k, 0, 0, n);
  116.   return 0;
  117. }
  118.  
Success #stdin #stdout 0s 27072KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mHow4n
O(k log^2 k) dynamic connectivity problem
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!