Guest User

Untitled

a guest
Sep 10th, 2015
520
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <sstream>
  4.  
  5. #include <vector>
  6. #include <set>
  7. #include <bitset>
  8. #include <map>
  9. #include <deque>
  10. #include <string>
  11.  
  12. #include <algorithm>
  13. #include <numeric>
  14.  
  15. #include <cstdio>
  16. #include <cassert>
  17. #include <cstdlib>
  18. #include <cstring>
  19. #include <ctime>
  20. #include <cmath>
  21.  
  22. #define pb push_back
  23. #define pbk pop_back
  24. #define mp make_pair
  25. #define fs first
  26. #define sc second
  27. #define all(x) (x).begin(), (x).end()
  28. #define foreach(i, a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); ++i)
  29. #define len(a) ((int) (a).size())
  30.  
  31. #ifdef CUTEBMAING
  32. #define eprintf(...) fprintf(stderr, __VA_ARGS__)
  33. #else
  34. #define eprintf(...) 42
  35. #endif
  36.  
  37. using namespace std;
  38.  
  39. typedef long long int64;
  40. typedef long double ld;
  41. typedef unsigned long long lint;
  42.  
  43. const int inf = (1 << 30) - 1;
  44. const int64 linf = (1ll << 62) - 1;
  45. const int N = 5e5 + 100;
  46. const int K = 50;
  47.  
  48. struct cooldsu {
  49.     int parent[N], rank[N], parity[N];
  50.     int flag = 0;
  51.     vector<pair<int*, int>> changes;
  52.  
  53.     void init(int n) {
  54.         for (int i = 0; i < n; i++) {
  55.             parent[i] = i, rank[i] = 0, parity[i] = 0;
  56.         }
  57.     }
  58.  
  59.     int size() { return changes.size(); }
  60.  
  61.     void set(int *a, int b) { changes.push_back(mp(a, *a)), *a = b; }
  62.  
  63.     void revert(int len) {
  64.         while (len(changes) > len) {
  65.             *changes.back().fs = changes.back().sc, changes.pop_back();
  66.         }
  67.     }
  68.  
  69.     pair<int, int> findSetAndParity(int v) {
  70.         int curParity = 0;
  71.         while (parent[v] != v) {
  72.             curParity ^= parity[v], v = parent[v];
  73.         }
  74.         return mp(v, curParity);
  75.     }
  76.  
  77.     void unite(int a, int b) {
  78.         pair<int, int> pa = findSetAndParity(a), pb = findSetAndParity(b);
  79.         if (pa.fs == pb.fs) {
  80.             if (!flag && pa.sc == pb.sc) {
  81.                 set(&flag, 1);
  82.             }
  83.             return ;
  84.         }
  85.         if (rank[pa.fs] == rank[pb.fs]) {
  86.             set(rank + pa.fs, rank[pa.fs] + 1);
  87.         }
  88.         if (rank[pa.fs] > rank[pb.fs]) {
  89.             swap(pa, pb);
  90.         }
  91.         set(parent + pa.fs, pb.fs), set(parity + pa.fs, pa.sc ^ pb.sc ^ 1);
  92.     }
  93. };
  94.  
  95. vector<pair<int, int>> rmq[N * 4 + 100];
  96.  
  97. cooldsu dsu[K];
  98.  
  99. int n, m, k, q;
  100. int a[N], b[N];
  101. int e[N], c[N];
  102. int nextRequest[N], last[N];
  103. int curColor[N];
  104.  
  105. void update(int i, int ll, int rr, int l, int r, const pair<int, int> &add) {
  106.     if (ll > r || rr < l) {
  107.         return ;
  108.     }
  109.     if (l <= ll && rr <= r) {
  110.         return void (rmq[i].push_back(add));
  111.     }
  112.     update(i * 2, ll, (ll + rr) / 2, l, r, add);
  113.     update(i * 2 + 1, (ll + rr) / 2 + 1, rr, l, r, add);
  114. }
  115.  
  116. void solve(int i, int l, int r) {
  117.     vector<int> ln(len(rmq[i]));
  118.     for (int j = 0; j < len(ln); j++) {
  119.         ln[j] = len(dsu[rmq[i][j].sc]);
  120.     }
  121.     for (auto upd : rmq[i]) {
  122.         dsu[upd.sc].unite(a[upd.fs], b[upd.fs]);
  123.     }
  124.     if (l == r) {
  125.         int edge = e[l], color = c[l];
  126.         int u = a[edge], v = b[edge];
  127.         pair<int, int> a = dsu[color].findSetAndParity(u), b = dsu[color].findSetAndParity(v);
  128.         if (a != b) {
  129.             puts("YES");
  130.             update(1, 0, q - 1, l + 1, nextRequest[l] - 1, mp(edge, color));
  131.             curColor[edge] = color;
  132.         } else {
  133.             puts("NO");
  134.             if (curColor[edge] != -1) {
  135.                 update(1, 0, q - 1, l + 1, nextRequest[l] - 1, mp(edge, curColor[edge]));
  136.             }
  137.         }
  138.     } else {
  139.         solve(i * 2, l, (l + r) / 2);
  140.         solve(i * 2 + 1, (l + r) / 2 + 1, r);
  141.     }
  142.     for (int j = 0; j < len(ln); j++) {
  143.         dsu[rmq[i][j].sc].revert(ln[j]);
  144.     }
  145. }
  146.  
  147. int main() {
  148.     cin >> n >> m >> k >> q;
  149.     for (int i = 0; i < k; i++) {
  150.         dsu[i].init(n);
  151.     }
  152.     for (int i = 0; i < m; i++) {
  153.         scanf("%d%d", &a[i], &b[i]), a[i]--, b[i]--;
  154.         curColor[i] = -1;
  155.     }
  156.     for (int i = 0; i < q; i++) {
  157.         scanf("%d%d", &e[i], &c[i]), e[i]--, c[i]--;
  158.     }
  159.     fill_n(last, m, inf);
  160.     for (int i = q - 1; i >= 0; i--) {
  161.         nextRequest[i] = last[e[i]];
  162.         last[e[i]] = i;
  163.     }
  164.     solve(1, 0, q - 1);
  165.     return 0;
  166. }
RAW Paste Data