Advertisement
Guest User

Untitled

a guest
Feb 17th, 2018
1,442
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.66 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement