fork(11) download
  1. /**
  2.  * Author: Sergey Kopeliovich (Burunduk30@gmail.com)
  3.  * Date: 2013.09.08
  4.  */
  5.  
  6. #include <cstdio>
  7. #include <cassert>
  8. #include <algorithm>
  9. #include <vector>
  10. #include <map>
  11.  
  12. using namespace std;
  13.  
  14. #define forn(i, n) for (int i = 0; i < (int)(n); i++)
  15. #define forit(i, a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); i++)
  16. #define pb push_back
  17. #define mp make_pair
  18. #define sz(a) (int)(a).size()
  19.  
  20. typedef vector <int> vi;
  21. typedef pair <int, int> pii;
  22.  
  23. const int N = (int)3e5;
  24.  
  25. struct edge
  26. {
  27. int a, b, l, r;
  28. };
  29. typedef vector <edge> List;
  30.  
  31. int cnt[N + 1], ans[N], u[N], color[N], deg[N];
  32. vi g[N];
  33.  
  34. void add( int a, int b )
  35. {
  36. g[a].pb(b), g[b].pb(a);
  37. }
  38.  
  39. void dfs( int v, int value )
  40. {
  41. u[v] = 1, color[v] = value;
  42. forn(i, sz(g[v]))
  43. if (!u[g[v][i]])
  44. dfs(g[v][i], value);
  45. }
  46.  
  47. void go( int l, int r, const List &v, int vn, int add_vn ) // [l, r)
  48. {
  49. if (cnt[l] == cnt[r])
  50. return; // no queries, only changes
  51. if (!sz(v))
  52. {
  53. while (l < r)
  54. ans[l++] = vn + add_vn;
  55. return;
  56. }
  57.  
  58. List v1;
  59. forn(i, vn)
  60. g[i].clear();
  61. forn(i, sz(v))
  62. if (v[i].a != v[i].b)
  63. {
  64. if (v[i].l <= l && r <= v[i].r)
  65. add(v[i].a, v[i].b);
  66. else if (l < v[i].r && v[i].l < r)
  67. v1.pb(v[i]);
  68. }
  69.  
  70. int vn1 = 0;
  71. forn(i, vn)
  72. u[i] = 0;
  73. forn(i, vn)
  74. if (!u[i])
  75. deg[vn1] = 0, dfs(i, vn1++);
  76.  
  77. forn(i, sz(v1))
  78. {
  79. v1[i].a = color[v1[i].a];
  80. v1[i].b = color[v1[i].b];
  81. if (v1[i].a != v1[i].b)
  82. deg[v1[i].a]++, deg[v1[i].b]++;
  83. }
  84.  
  85. vn = vn1, vn1 = 0;
  86. forn(i, vn)
  87. u[i] = vn1, vn1 += (deg[i] > 0), add_vn += !deg[i];
  88. forn(i, sz(v1))
  89. {
  90. v1[i].a = u[v1[i].a];
  91. v1[i].b = u[v1[i].b];
  92. }
  93.  
  94. int m = (l + r) / 2; // [l, m) [m, r)
  95. go(l, m, v1, vn1, add_vn);
  96. go(m, r, v1, vn1, add_vn);
  97. }
  98.  
  99. int main()
  100. {
  101. #define NAME "connect"
  102. assert(freopen(NAME ".in", "r", stdin));
  103. assert(freopen(NAME ".out", "w", stdout));
  104.  
  105. map <pii, int> m;
  106. List v;
  107. int n, k;
  108. scanf("%d%d", &n, &k);
  109. forn(i, k)
  110. {
  111. char type;
  112. scanf(" %c", &type);
  113. if (type == '+' || type == '-')
  114. {
  115. int a, b;
  116. scanf("%d%d", &a, &b), a--, b--;
  117. if (a == b) // loop
  118. {
  119. k--, i--;
  120. continue;
  121. }
  122. if (a > b)
  123. swap(a, b);
  124.  
  125. if (type == '+')
  126. m[mp(a, b)] = i;
  127. else
  128. {
  129. int &j = m[mp(a, b)];
  130. v.pb({a, b, j, i});
  131. j = -1;
  132. }
  133. }
  134. else
  135. cnt[i + 1]++;
  136. cnt[i + 1] += cnt[i];
  137. }
  138. forit(it, m)
  139. if (it->second != -1)
  140. v.pb({it->first.first, it->first.second, it->second, k});
  141.  
  142. go(0, k, v, n, 0);
  143.  
  144. forn(i, k)
  145. if (cnt[i + 1] != cnt[i])
  146. printf("%d\n", ans[i]);
  147. return 0;
  148. }
  149.  
Runtime error #stdin #stdout #stderr 0s 12848KB
stdin
Standard input is empty
stdout
Standard output is empty
stderr
prog: prog.cpp:102: int main(): Assertion `freopen("connect" ".in", "r", stdin)' failed.