fork download
copy 
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <math.h>
  4. #include <string.h>
  5. #include <time.h>
  6. #include <stdlib.h>
  7. #include <string>
  8. #include <bitset>
  9. #include <vector>
  10. #include <set>
  11. #include <map>
  12. #include <queue>
  13. #include <algorithm>
  14. #include <sstream>
  15. #include <stack>
  16. #include <iomanip>
  17. using namespace std;
  18. #define pb push_back
  19. #define mp make_pair
  20. typedef pair<int,int> pii;
  21. typedef long long ll;
  22. typedef double ld;
  23. typedef vector<int> vi;
  24. #define fi first
  25. #define se second
  26. #define fe first
  27. #define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
  28. #define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
  29. #define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
  30. #define es(x,e) (int e=fst[x];e;e=nxt[e])
  31. #define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
  32. #define SZ 666666
  33. int T,n,q,v[SZ],rs[SZ]; Edg
  34. #define SS 4209999
  35. int sz[SS],ch[SS][2],an=0;
  36. int ins(int x,int l,int r,int p)
  37. {
  38. 	int y=++an; sz[y]=sz[x]+1;
  39. 	if(l==r) return y;
  40. 	int m=(l+r)>>1;
  41. 	if(p<=m)
  42. 		ch[y][1]=ch[x][1],
  43. 		ch[y][0]=ins(ch[x][0],l,m,p);
  44. 	else
  45. 		ch[y][0]=ch[x][0],
  46. 		ch[y][1]=ins(ch[x][1],m+1,r,p);
  47. 	return y;
  48. }
  49. int d1[SZ],rv[SZ],ls[SZ],C=0;
  50. void dfs(int x,int f=0)
  51. {
  52. 	d1[x]=++C; rv[C]=x;
  53. 	for esb(x,e,b) if(b!=f)
  54. 		dfs(b,x);
  55. 	ls[x]=C;
  56. }
  57. int qry(int r1,int r2,int s,int g)
  58. {
  59. 	if(s<0)
  60. 		return 0;
  61. 	int w=(g>>s)&1;
  62. 	if(ch[r2][!w]!=ch[r1][!w])
  63. 		return qry(ch[r1][!w],ch[r2][!w],s-1,g)^(1<<s);
  64. 	return qry(ch[r1][w],ch[r2][w],s-1,g);
  65. }
  66. struct RMQ
  67. {
  68. vector<int> a1,a2,mi; int*A1;
  69. int S=0;
  70. int M;
  71. void pb(pii x)
  72. {
  73. 	if(!a1.size()) a1.pb(0);
  74. 	if(!a2.size()) a2.pb(0);
  75. 	++S; a1.pb(x.fi); a2.pb(x.se);
  76. }
  77. void build()
  78. {
  79. 	if(M||(!S)) return;
  80. 	M=1; while(M<S+2) M<<=1;
  81. 	mi.resize(M+M+1);
  82. 	if(!is_sorted(&a1[1],&a1[S])) throw "GG";
  83. 	for(int i=0;i<=M+M;++i) mi[i]=2e9;
  84. 	for(int i=1;i<=S;++i) mi[i+M]=a2[i];
  85. 	for(int i=M-1;i>=1;--i)
  86. 		mi[i]=min(mi[i+i],mi[i+i+1]);
  87. 	A1=&a1[0];
  88. }
  89. void clr()
  90. {
  91. 	M=S=0; a1.clear(); a2.clear(); mi.clear();
  92. }
  93. int qmin(int l,int r)
  94. {
  95. 	int L=lower_bound(A1+1,A1+S,l)-A1,
  96. 	R=lower_bound(A1+1,A1+1+S,r+1)-A1-1,
  97. 	ans=2e9;
  98. 	if(L>R) throw "GG";
  99. 	l=L; r=R;
  100. 	for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1)
  101. 	{
  102. 		if(~l&1) ans=min(ans,mi[l^1]);
  103. 		if(r&1) ans=min(ans,mi[r^1]);
  104. 	}
  105. 	return ans;
  106. }
  107. }sb[1<<20];
  108. namespace FF{
  109. char ch,B[1<<20],*S=B,*T=B;
  110. #define getc() (S==T&&(T=(S=B)+fread(B,1,1<<20,stdin),S==T)?0:*S++)
  111. #define isd(c) (c>='0'&&c<='9')
  112. int aa,bb;int F(){
  113.     while(ch=getc(),!isd(ch)&&ch!='-');ch=='-'?aa=bb=0:(aa=ch-'0',bb=1);
  114.     while(ch=getc(),isd(ch))aa=aa*10+ch-'0';return bb?aa:-aa;
  115. }
  116. }
  117. #define gi FF::F()
  118. #define BUFSIZE 5000000
  119. namespace fob {char b[BUFSIZE]={},*f=b,*g=b+BUFSIZE-2;}
  120. #define pob (fwrite(fob::b,sizeof(char),fob::f-fob::b,stdout),fob::f=fob::b,0)
  121. #define pc(x) (*(fob::f++)=(x),(fob::f==fob::g)?pob:0)
  122. struct foce {~foce() {pob; fflush(stdout);}} _foce;
  123. namespace ib {char b[100];}
  124. inline void pint(int x)
  125. {
  126.     if(x==0) {pc(48); return;}
  127.     if(x<0) {pc('-'); x=-x;}
  128.     char *s=ib::b;
  129.     while(x) *(++s)=x%10, x/=10;
  130.     while(s!=ib::b) pc((*(s--))+48);
  131. }
  132. void sol()
  133. {
  134. 	n=gi,q=gi; M=C=an=0;
  135. 	for(int i=1;i<=n;++i)
  136. 		fst[i]=0,v[i]=gi;
  137. 	for(int i=1,a,b;i<n;++i) adde(a=gi,b=gi);
  138. 	dfs(1);
  139. 	for(int i=1;i<=n;++i)
  140. 		sb[v[rv[i]]].pb(pii(i,rv[i]));
  141. 	for(int i=1;i<=n;++i)
  142. 		sb[v[rv[i]]].build();
  143. 	for(int i=1;i<=n;++i)
  144. 		rs[i]=ins(rs[i-1],0,(1<<20)-1,v[rv[i]]);
  145. 	int la=0,ln=0;
  146. 	for(int i=0;i<q;++i)
  147. 	{
  148. 		int vv=gi,k=gi;
  149. 		vv^=ln; k^=la;
  150. 		int L=d1[vv],R=ls[vv];
  151. 		int w=qry(rs[L-1],rs[R],19,k);
  152. 		la=w; ln=sb[w^k].qmin(L,R);
  153. 		pint(ln); pc(' ');
  154. 		pint(la); pc('\n');
  155. 	}
  156. 	for(int i=1;i<=n;++i)
  157. 		sb[v[i]].clr();
  158. }
  159. int main()
  160. {
  161. 	T=gi;
  162. //	scanf("%d",&T);
  163. 	while(T--) sol();
  164. }
Time limit exceeded #stdin #stdout 5s 181440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/quPOK2
language:
C++14 (gcc 8.3)
created:
5 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!