daily pastebin goal
57%
SHARE
TWEET

Untitled

a guest Feb 17th, 2018 334 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef pair<pair<int, int>, int> edge;
  6.  
  7. #define x first
  8. #define y second
  9.  
  10. const int M = 2000043;
  11. const int N = 200043;
  12. const int B = 30;
  13. const int IDX = 200002;
  14.  
  15. int* where[M];
  16. int val[M];
  17. int st = 0;
  18.  
  19. inline void rollback(int new_st)
  20. {
  21.     while(st != new_st)
  22.     {
  23.         st--;
  24.         (*where[st]) = val[st];
  25.     }
  26. }
  27.  
  28. inline void change(int& address, int new_val)
  29. {
  30.     where[st] = &address;
  31.     val[st] = address;
  32.     st++;
  33.     address = new_val;
  34. }
  35.  
  36. vector<edge> T[4 * N];
  37. vector<edge> Q[4 * N];
  38. int ans[N];
  39.  
  40. void add_edge(int v, int l, int r, int L, int R, edge e)
  41. {
  42.     if (L >= R)
  43.         return;
  44.     if (l == L && r == R)
  45.     {
  46.         T[v].push_back(e);
  47.         return;
  48.     }
  49.     int mid = (l + r) >> 1;
  50.     add_edge(v * 2 + 1, l, mid, L, min(mid, R), e);
  51.     add_edge(v * 2 + 2, mid, r, max(L, mid), R, e);
  52. }
  53.  
  54. int base[B];
  55.  
  56. inline void try_gauss(int v)
  57. {
  58.     for(int i = 29; i >= 0; i--)
  59.         if (base[i] != -1 && (v & (1 << i)))
  60.             v ^= base[i];
  61.     if (v != 0)
  62.         for(int i = 29; i >= 0; i--)
  63.             if (v & (1 << i))
  64.                 return change(base[i], v);
  65. }
  66.  
  67. int rnk[N];
  68. int dsu[N];
  69. int dist[N];
  70.  
  71. inline int get_p(int x)
  72. {  
  73.     while(dsu[x] != x)
  74.         x = dsu[x];
  75.     return x;
  76. }
  77.  
  78. inline int get_dist(int x)
  79. {
  80.     int res = 0;
  81.     while(dsu[x] != x)
  82.     {
  83.         res ^= dist[x];
  84.         x = dsu[x];
  85.     }
  86.     return res;
  87. }
  88.  
  89. inline bool merge(int x, int y, int d)
  90. {
  91.     int dist_x = get_dist(x);
  92.     int dist_y = get_dist(y);
  93.     x = get_p(x);
  94.     y = get_p(y);
  95.     if (x == y)
  96.         return false;
  97.     d ^= (dist_x ^ dist_y);
  98.     if (rnk[x] < rnk[y])
  99.         swap(x, y);
  100.     change(dsu[y], x);
  101.     change(rnk[x], rnk[x] + rnk[y]);
  102.     change(dist[y], d);
  103.     return true;
  104. }
  105.  
  106. inline void process(int v)
  107. {
  108.     for(auto x : T[v])
  109.         if (!merge(x.x.x, x.x.y, x.y))
  110.         {
  111.             int cycle_len = x.y ^ get_dist(x.x.x) ^ get_dist(x.x.y);
  112.             try_gauss(cycle_len);
  113.         }
  114. }
  115.  
  116. inline int answer(int x, int y)
  117. {
  118.     int d = get_dist(x) ^ get_dist(y);
  119.     for(int i = 29; i >= 0; i--)
  120.         if (base[i] != -1 && (d & (1 << i)))
  121.             d ^= base[i];
  122.     return d;
  123. }
  124.  
  125. void dfs(int v, int l, int r)
  126. {
  127.     int rollback_to = st;
  128.     process(v);
  129.     if (l == r - 1)
  130.     {
  131.         for(auto x : Q[v])
  132.             ans[x.y] = answer(x.x.x, x.x.y);
  133.     }
  134.     else
  135.     {
  136.         int mid = (l + r) >> 1;
  137.         dfs(v * 2 + 1, l, mid);
  138.         dfs(v * 2 + 2, mid, r);    
  139.     }
  140.     rollback(rollback_to);
  141. }
  142.  
  143. void add_query(int v, int l, int r, int pos, edge e)
  144. {
  145.     if (l == r - 1)
  146.         Q[v].push_back(e);
  147.     else
  148.     {
  149.         int mid = (l + r) >> 1;
  150.         if (pos < mid)
  151.             add_query(v * 2 + 1, l, mid, pos, e);
  152.         else
  153.             add_query(v * 2 + 2, mid, r, pos, e);
  154.     }
  155. }
  156.  
  157. int main() {
  158.     int n, m;
  159.     scanf("%d %d", &n, &m);
  160.     for(int i = 0; i < n; i++)
  161.     {
  162.         dsu[i] = i;
  163.         dist[i] = 0;
  164.         rnk[i] = 1;
  165.     }
  166.     int cur = 0;
  167.     map<pair<int, int>, pair<int, int> > z;
  168.     for(int i = 0; i < m; i++)
  169.     {
  170.         int x, y, d;
  171.         scanf("%d %d %d", &x, &y, &d);
  172.         --x;
  173.         --y;
  174.         z[make_pair(x, y)] = make_pair(0, d);
  175.     }
  176.     int cnt_q = 0;
  177.     int q;
  178.     scanf("%d", &q);
  179.     for(int i = 0; i < q; i++)
  180.     {
  181.         int t;
  182.         scanf("%d", &t);
  183.         if (t == 1)
  184.         {
  185.             int x, y, d;
  186.             scanf("%d %d %d", &x, &y, &d);
  187.             cur++;
  188.             --x;
  189.             --y;
  190.             z[make_pair(x, y)] = make_pair(cur, d);
  191.         }
  192.         if (t == 2)
  193.         {
  194.             int x, y;
  195.             scanf("%d %d", &x, &y);
  196.             --x;
  197.             --y;
  198.             cur++;
  199.             add_edge(0, 0, IDX, z[make_pair(x, y)].x, cur, make_pair(make_pair(x, y), z[make_pair(x, y)].y));
  200.             z.erase(make_pair(x, y));
  201.         }
  202.         if (t == 3)
  203.         {
  204.             int x, y;
  205.             scanf("%d %d", &x, &y);
  206.             --x;
  207.             --y;
  208.             add_query(0, 0, IDX, cur, make_pair(make_pair(x, y), cnt_q));
  209.             cnt_q++;
  210.         }
  211.     }
  212.     cur++;
  213.     for(auto x : z)
  214.         add_edge(0, 0, IDX, x.y.x, cur, make_pair(x.x, x.y.y));
  215.     dfs(0, 0, IDX);
  216.     for(int i = 0; i < cnt_q; i++)
  217.         printf("%d\n", ans[i]);
  218.     return 0;
  219. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top