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