fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #define ll long long
  5. using namespace std;
  6. typedef pair<int, int> ii;
  7. const ll MX = 2e5+10, LG = 20;
  8. vector<vector<ii> > adj(MX);
  9. ll p[LG][MX];
  10. ll g[MX], rk[MX], sz[MX];
  11. ll d[MX], depth[MX];
  12.  
  13. void init(ll x) {
  14. 	g[x] = x;
  15. 	rk[x] = 0;
  16. 	sz[x] = 1;
  17. 	d[x] = 0;
  18. 	depth[x] = 0;
  19. }
  20.  
  21. ll find(ll x) {
  22. 	return (g[x] == x ? x : g[x] = find(g[x]));
  23. }
  24.  
  25. void merge(ll x, ll y) {
  26. 	ll GX = find(x), GY = find(y);
  27. 	if (rk[GX] > rk[GY]) {
  28. 		g[GY] = GX;
  29. 		sz[GX] += sz[GY];
  30. 	}
  31. 	else {
  32. 		g[GX] = GY;
  33. 		sz[GY] += sz[GX];
  34. 	}
  35. 	if (rk[GX] == rk[GY]) {
  36. 		rk[GY]++;
  37. 	}
  38. }
  39.  
  40. ll size(ll x) {
  41. 	return sz[find(x)];
  42. }
  43.  
  44. vector<int> vertices;
  45. void dfs(ll u, ll prev) {
  46. 	vertices.push_back(u);
  47. 	for (ll i = 0; i < adj[u].size(); i++) {
  48. 		ll v = adj[u][i].first;
  49. 		if (v != prev) {
  50. 			depth[v] = depth[u]+1;
  51. 			d[v] = d[u]+adj[u][i].second;
  52. 			dfs(v, u);
  53. 		}
  54. 	}
  55. }
  56.  
  57. ll LCA(ll u, ll v) {
  58. 	if (find(u) != find(v)) {
  59. 		return -1;
  60. 	}
  61. 	if (depth[u] > depth[v]) {
  62. 		swap(u, v);
  63. 	}
  64. 	for (ll i = LG-1; i >= 0; i--) {
  65. 		if ((int)(1<<i) <= depth[v]-depth[u]) {
  66. 			v = p[i][v];
  67. 		}
  68. 	}
  69. 	if (u == v) return u;
  70. 	for (ll i = LG-1; i >= 0; i--) {
  71. 		if (p[i][u] != p[i][v]) {
  72. 			u = p[i][u];
  73. 			v = p[i][v];
  74. 		}
  75. 	}
  76. 	return p[0][u];
  77. }
  78.  
  79. ll dist(ll u, ll v) {
  80. 	if (find(u) != find(v)) {
  81. 		return -1;
  82. 	}
  83. 	ll lca = LCA(u, v);
  84. 	return d[u]+d[v]-2*d[lca];
  85. }
  86.  
  87. void dominate(ll u, ll v, ll c) {
  88. 	ll cur = v, parent = p[0][cur];
  89. 	while (parent != -1) {
  90. 		ll nw = p[0][parent];
  91. 		p[0][parent] = cur;
  92. 		cur = parent;
  93. 		parent = nw;
  94. 	}
  95. 	p[0][v] = u;
  96. 	vertices.clear();
  97. 	depth[v] = depth[u]+1;
  98. 	d[v] = d[u]+c;
  99. 	dfs(v, v);
  100.  
  101. 	for (ll i = 1; i < LG; i++) {
  102. 		for (ll j = 0; j < vertices.size(); j++) {
  103. 			ll k = vertices[j];
  104. 			if (p[i-1][k] != -1) {
  105. 				p[i][k] = p[i-1][p[i-1][k]];
  106. 			}
  107. 			else {
  108. 				p[i][k] = -1;
  109. 			}
  110. 		}
  111. 	}
  112. }
  113.  
  114. int main() {
  115. 	ios_base::sync_with_stdio(false); cin.tie(0);
  116. 	ll n, q; cin >> n >> q;
  117. 	for (ll i = 0; i < MX; i++) {
  118. 		init(i);
  119. 	}
  120. 	for (ll i = 0; i < LG; i++) for (ll j = 0; j < MX; j++) {
  121. 		p[i][j] = -1;
  122. 	}
  123. 	ll ans = 0;
  124. 	while (q--) {
  125. 		ll tp, u, v, c;
  126. 		cin >> tp >> u >> v;
  127. 		u = (u+ans)%n+1;
  128. 		v = (v+ans)%n+1;
  129. 		if (tp == 1) {
  130. 			cin >> c;
  131. 			if (size(u) < size(v)) {
  132. 				swap(u, v);
  133. 			}
  134. 			dominate(u, v, c);
  135. 			adj[u].push_back(ii(v, c));
  136. 			adj[v].push_back(ii(u, c));
  137. 			merge(u, v);
  138. 		}
  139. 		else {
  140. 			cout << dist(u, v) << '\n';
  141. 			ans = dist(u, v);
  142. 		}
  143. 	}
  144. 	return 0;
  145. }
Runtime error #stdin #stdout 0.01s 44880KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hOztrW
language:
C++14 (gcc 8.3)
created:
7 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!