fork download 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define fi first
  9. #define se second
  10. #define mp make_pair
  11. #define pb push_back
  12. #define fbo find_by_order
  13. #define ook order_of_key
  14.  
  15. typedef long long ll;
  16. typedef pair<ll,ll> ii;
  17. typedef vector<int> vi;
  18. typedef long double ld; 
  19. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  20. typedef set<int>::iterator sit;
  21. typedef map<int,int>::iterator mit;
  22. typedef vector<int>::iterator vit;
  23.  
  24. const int LG = 18;
  25. const int N = 200010;
  26. int st[LG][N];
  27. ll h[N];
  28. ll sumh[N];
  29. vector<ii> adj[N];
  30. vector<ii> adj2[N];
  31. int sum[N];
  32.  
  33. int rt(int u)
  34. {
  35. 	for(int i = LG - 1; i >= 0; i--)
  36. 	{
  37. 		if(st[i][u]!=-1) u=st[i][u];
  38. 	}
  39. 	return u;
  40. }
  41.  
  42. void merge(int u, int v)
  43. {
  44. 	u = rt(u); v = rt(v);
  45. 	if(u == v) return ;
  46. 	sum[u]+=sum[v];
  47. 	sum[v]=0;
  48. }
  49.  
  50. int lca(int u, int v)
  51. {
  52. 	if(h[u] > h[v]) swap(u, v);
  53. 	for(int i = LG - 1; i >= 0; i--)
  54. 	{
  55. 		if(st[i][v] != -1 && h[st[i][v]] >= h[u])
  56. 		{
  57. 			v = st[i][v];
  58. 		}
  59. 	}
  60. 	if(u == v) return u;
  61. 	for(int i = LG - 1; i >= 0; i--)
  62. 	{
  63. 		if(st[i][v] != -1 && st[i][v] != st[i][u])
  64. 		{
  65. 			u = st[i][u];
  66. 			v = st[i][v];
  67. 		}
  68. 	}
  69. 	return st[0][u];
  70. }
  71.  
  72. bool sameset(int u, int v)
  73. {
  74. 	return (rt(u)==rt(v));
  75. }
  76.  
  77. ll dist(int u, int v)
  78. {
  79. 	if(sameset(u,v)) return (sumh[u] + sumh[v] - sumh[lca(u,v)]*2LL);
  80. 	else return -1;
  81. }
  82.  
  83. void dfs(int u, int p, int nw, int hh, ll sm)
  84. {
  85. 	adj[u].clear();
  86. 	if(p == -1) 
  87. 	{
  88. 		h[u] = hh;
  89. 		sumh[u] = sm;
  90. 	}
  91. 	else
  92. 	{
  93. 		h[u] = h[p] + 1;
  94. 	}
  95. 	if(p == -1) st[0][u] = nw;
  96. 	else st[0][u] = p;
  97. 	for(int i = 1; i < LG; i++)
  98. 	{
  99. 		if(st[i-1][u] == -1) st[i][u] = -1;
  100. 		else st[i][u] = st[i-1][st[i-1][u]];
  101. 	}
  102. 	for(int i = 0; i < adj2[u].size(); i++)
  103. 	{
  104. 		int v = adj2[u][i].fi; ll w = adj2[u][i].se;
  105. 		if(v==p) continue;
  106. 		if(p==-1&&v==nw) continue;
  107. 		sumh[v] = sumh[u] + w;
  108. 		adj[u].pb(mp(v, w));
  109. 		dfs(v, u, nw, hh, sm);
  110. 	}	
  111. }
  112.  
  113. void join(int u, int v, ll w) //order is important here
  114. {
  115. 	if(sum[rt(u)]<sum[rt(v)]) swap(u, v);
  116. 	//cerr<<sum[rt(u)]<<' '<<sum[rt(v)]<<'\n';
  117. 	merge(u,v);
  118. 	dfs(v, -1, u, h[u] + 1, sumh[u] + w);
  119. 	adj2[u].pb(mp(v,w)); adj2[v].pb(mp(u,w));
  120. 	adj[u].pb(mp(v,w));
  121. }
  122.  
  123. int main()
  124. {
  125. 	ios_base::sync_with_stdio(0); cin.tie(0);
  126. 	int n, q; 
  127. 	cin>>n>>q;
  128. 	memset(st,-1,sizeof(st));
  129. 	for(int i = 0; i < n; i++) sum[i] = 1;
  130. 	ll lastans = 0;
  131. 	for(int i = 0; i < q; i++)
  132. 	{
  133. 		int t, u, v;
  134. 		cin>>t>>u>>v;
  135. 		u=(u+lastans)%n + 1;
  136. 		v=(v+lastans)%n + 1;
  137. 		u--; v--;
  138. 		//cerr<<"U V : "<<u+1<<' '<<v+1<<'\n';
  139. 		if(t==1)
  140. 		{
  141. 			ll w; cin >> w;
  142. 			assert(rt(u)!=rt(v));
  143. 			join(u,v,w);
  144. 			//cout<<"DONE\n";
  145. 		}
  146. 		else
  147. 		{
  148. 			ll aa = dist(u,v);
  149. 			cout<<aa<<'\n';
  150. 			lastans = (aa%n);
  151. 			if(aa<0) aa+=n;
  152. 		}
  153. 	}
  154. }
  155.  
Runtime error #stdin #stdout 0s 26128KB
comments ()
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/2quuZM
language:
C++14 (gcc 8.3)
created:
8 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!