fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pb push_back
  5. #define mp make_pair
  6. #define ff first
  7. #define ss second
  8. #define int long long
  9.  
  10. #define trace1(x)                cerr<<#x<<": "<<x<<endl
  11. #define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
  12. #define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
  13. #define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
  14. #define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
  15. #define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
  16.  
  17. const int N=1e5+5;
  18. const int LG=19;
  19.  
  20. int n, m, q, ct=0;
  21. int a[N], root[N], level[N], parent[LG][N], st[20*N], lc[20*N], rc[20*N];
  22. vector<int> g[N];
  23.  
  24. int build(int L, int R)
  25. {
  26. 	int node=++ct;
  27. 	if(L==R)
  28. 	{
  29. 		st[node]=-1;
  30. 		return node;
  31. 	}
  32. 	int M=(L+R)>>1;
  33. 	lc[node]=build(L, M);
  34. 	rc[node]=build(M+1, R);
  35. 	return node;
  36. }
  37.  
  38. int update(int onode, int L, int R, int pos, int val)
  39. {
  40. 	int node=++ct;
  41. 	if(L==R)
  42. 	{
  43. 		st[node]=val;
  44. 		return node;
  45. 	}
  46. 	int M=(L+R)>>1;
  47. 	lc[node]=lc[onode];
  48. 	rc[node]=rc[onode];
  49. 	if(pos<=M)
  50. 	{
  51. 		lc[node]=update(lc[onode], L, M, pos, val);
  52. 	}
  53. 	else
  54. 	{
  55. 		rc[node]=update(rc[onode], M+1, R, pos, val);
  56. 	}
  57. 	return node;
  58. }
  59.  
  60. void dfs(int k, int par, int lvl)
  61. {
  62. 	int onode=root[par];
  63. 	root[k]=update(onode, 1, m, a[k], k);
  64. 	parent[0][k]=par;
  65. 	level[k]=lvl;
  66. 	for(auto it:g[k])
  67. 	{
  68. 		if(it==par)
  69. 			continue;
  70. 		dfs(it, k, lvl+1);
  71. 	}
  72. }
  73.  
  74. void precompute()
  75. {	
  76. 	for(int i=1;i<LG;i++)
  77. 	{
  78. 		for(int j=1;j<=n;j++)
  79. 		{
  80. 			if(parent[i-1][j])
  81. 				parent[i][j]=parent[i-1][parent[i-1][j]];
  82. 		}
  83. 	}
  84. }
  85.  
  86. int walk(int u, int k)
  87. {
  88. 	int diff=k;
  89. 	for(int i=LG-1;i>=0;i--)
  90. 	{
  91. 		if(diff&(1<<i))
  92. 		{
  93. 			u=parent[i][u];
  94. 		}
  95. 	}
  96. 	return u;
  97. }
  98.  
  99. int LCA(int u, int v)
  100. {
  101. 	if(level[u]<level[v])
  102. 		swap(u,v);
  103. 	int diff=level[u]-level[v];
  104. 	for(int i=LG-1;i>=0;i--)
  105. 	{
  106. 		if(diff&(1<<i))
  107. 		{
  108. 			u=parent[i][u];
  109. 		}
  110. 	}
  111. 	if(u==v)
  112. 		return u;
  113. 	for(int i=LG-1;i>=0;i--)
  114. 	{
  115. 		if(parent[i][u] && parent[i][u]!=parent[i][v])
  116. 		{
  117. 			u=parent[i][u];
  118. 			v=parent[i][v];
  119. 		}
  120. 	}
  121. 	return parent[0][u];
  122. }
  123.  
  124. int query(int node, int L, int R, int pos)
  125. {
  126. 	if(L==R)
  127. 	{
  128. 		return st[node];
  129. 	}
  130. 	int M=(L+R)>>1;
  131. 	if(pos<=M)
  132. 		return query(lc[node], L, M, pos);
  133. 	else
  134. 		return query(rc[node], M+1, R, pos);
  135. }
  136.  
  137. int32_t main()
  138. {
  139.  
  140. 	int t;
  141. 	cin>>t;
  142. 	while(t--)
  143. 	{
  144. 		memset(a, 0, sizeof(a));
  145. 		memset(st, 0, sizeof(st));
  146. 		memset(rc, 0, sizeof(rc));
  147. 		memset(lc, 0, sizeof(lc));
  148. 		memset(root, 0, sizeof(root));
  149. 		memset(level, 0, sizeof(level));
  150. 		memset(parent, 0, sizeof(parent));
  151. 		ct=0;
  152. 		cin>>n>>m>>q;
  153. 		m++;
  154. 		for(int i=1;i<=n;i++)
  155. 		{
  156. 			cin>>a[i];
  157. 		}
  158. 		for(int i=0;i<=N;i++)
  159. 		{
  160. 			g[i].clear();
  161. 		}
  162. 	    for(int i=1;i<=n-1;i++)
  163. 		{
  164. 		  	int u,v; 
  165. 		   	cin>>u>>v;
  166. 		   	g[u].pb(v);
  167. 		   	g[v].pb(u);
  168. 		}	
  169. 		root[0]=build(1, m);
  170. 		int ans=0;
  171. 		dfs(1, 0, 0);
  172. 		precompute();
  173. 		for(int i=1;i<=q;i++)
  174. 		{
  175. 			int p, v;
  176. 			cin>>p>>v;
  177. 			int u=1 + ((p^ans)%n + n)%n;
  178. 			int storeu=u;
  179. 			int storecol=a[u];
  180. 			int kth_ancestor=walk(u, v);
  181. 			if(kth_ancestor==0)
  182. 			{
  183. 				ans=-1;
  184. 			}
  185. 			else
  186. 			{
  187. 				int node=query(root[kth_ancestor], 1, m, storecol);
  188. 				if(node==-1)
  189. 					ans=-1;
  190. 				else
  191. 					ans=level[storeu]-level[node];
  192. 			}
  193. 			cout<<ans<<endl;
  194. 		}
  195. 	}
  196. 	return 0;
  197. }
  198.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.c:1:25: fatal error: bits/stdc++.h: No such file or directory
 #include <bits/stdc++.h>
                         ^
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/6SoPxY
language:
C (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!