fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define endl '\n'
  4.  
  5. int N,Q,R, key;
  6. const int MAXN = 3e5+5;
  7. struct Node{
  8. 	int child[2];
  9. 	Node(){child[0]=child[1]=-1;}
  10. };
  11. Node trie[MAXN*32+1];//all values are <=2^31-1, and we need an additional root node
  12. vector<int> g[MAXN];
  13. int trieRoot[MAXN];
  14. int val[MAXN];
  15. int parent[MAXN];
  16. int reverseMap[MAXN];
  17. int trieptr = 0;
  18. int add(int node, int value){
  19. 	//cout<<"ADDING "<<value<<endl;
  20. 	trie[++trieptr] = trie[node];//copy root
  21. 	int cur = trieptr;
  22. 	int newRoot = cur;
  23. 	for(int p = 30; p>=0; --p){//all values are <=2^31-1
  24. 		int bit = (value >> p) &1;
  25. 		++trieptr;
  26. 		if(trie[cur].child[bit]>=0){
  27. 			trie[trieptr] = trie[trie[cur].child[bit]]; //copy child
  28. 		}
  29. 		trie[cur].child[bit] = trieptr;
  30. 		cur = trieptr;
  31. 	}
  32. 	return newRoot;
  33. }
  34. int search(int node, int value){
  35. 	int cur = node;
  36. 	int ans = 0;
  37. 	for(int p = 30; p>=0; --p){//all values are <=2^31-1
  38. 		int bit = (value >> p) &1;
  39. 		if(trie[cur].child[bit]>=0){
  40. 			cur = trie[cur].child[bit];
  41. 			ans |= bit<<p;
  42. 		}else{
  43. 			cur = trie[cur].child[!bit];
  44. 			ans |= (!bit)<<p;
  45. 		}
  46. 	}
  47. 	return ans;
  48. }
  49.  
  50. int get_id(int x){
  51. 	static unordered_map<int,int> mp;
  52. 	if(!mp.count(x)){
  53. 		mp[x]=mp.size();
  54. 	}
  55. 	int id = mp[x];
  56. 	reverseMap[id] = x;
  57. 	return id;
  58. }
  59.  
  60. void dfs(int u, int p = -1){
  61. 	parent[u]=p;
  62. 	if(p!=-1){
  63. 		trieRoot[u] = add(trieRoot[p], val[u]);
  64. 	}
  65. 	for(int v: g[u]){
  66. 		if(v == p) continue;
  67. 		dfs(v,u);
  68. 	}
  69. }
  70.  
  71. void print(int node, int cur = 0, int depth = 0){
  72. 	if(trie[node].child[0]>=0){
  73. 		print(trie[node].child[0],(cur<<1) | 0, depth+1);
  74. 	}
  75. 	if(trie[node].child[1]>=0){
  76. 		print(trie[node].child[1],(cur<<1) | 1, depth +1);
  77. 	}
  78. 	if(trie[node].child[0] < 0 && trie[node].child[1] < 0){
  79. 		cout<<"IN SET: "<<cur<<" "<<depth<<endl;
  80. 	}
  81. }
  82.  
  83. int main() {
  84. 	ios::sync_with_stdio(false);
  85. 	cin.tie(0);
  86.  
  87. 	cin >> N >> Q;
  88. 	cin >> R >> key;
  89. 	R = get_id(R);
  90. 	val[R] = key;
  91.  
  92. 	for (int i = 0; i < N - 1; i++)
  93. 	{
  94. 		int u,v,k;
  95. 	    cin >> u >> v >> k;
  96. 	    u = get_id(u);
  97. 	    v = get_id(v);
  98. 	    g[u].push_back(v);
  99. 	    g[v].push_back(u);
  100. 	    val[u]=k;
  101. 	}
  102. 	trieRoot[R] = add(0,key);
  103. 	dfs(R);
  104.  
  105. 	int last_answer = 0;
  106.  
  107. 	int cntNodes = N;
  108. 	for (int i = 0; i < Q; i++)
  109. 	{
  110. 		int t;
  111. 	    cin >> t;
  112.  
  113. 	    // find real value of t
  114. 	    t ^= last_answer;
  115.  
  116. 	    if (t == 0)
  117. 	    {
  118. 	    	int v,u,k;
  119. 	        cin >> v >> u >> k;
  120.  
  121. 	        // find real values for u, v, and k
  122. 	        u ^= last_answer;
  123. 	        v ^= last_answer;
  124. 	        k ^= last_answer;
  125. 	        //cout<<"Q: "<<t<<" "<<v<<" "<<u<<" "<<k<<endl;
  126. 	        u = get_id(u);
  127. 	        v = get_id(v);
  128. 	        trieRoot[u] = add(trieRoot[v],k);
  129. 	        ++cntNodes;
  130. 	    }
  131. 	    else
  132. 	    {
  133. 	    	int v,k;
  134. 	        cin >> v >> k;
  135.  
  136. 	        // find real values for v, and k
  137. 	        v ^= last_answer;
  138. 	        k ^= last_answer;
  139.  
  140. 	        //cout<<"Q: "<<t<<" "<<v<<" "<<k<<endl;
  141.  
  142. 	        v = get_id(v);
  143.  
  144. 	        // compute the requested values
  145.  
  146. 	        int min_answer = k^search(trieRoot[v],k);//
  147. 	        int max_answer = k^search(trieRoot[v],~k);//
  148.  
  149. 	        cout<<min_answer<<" "<<max_answer<<endl;
  150.  
  151. 	        // update last_answer
  152. 	        last_answer = min_answer ^ max_answer;  
  153. 	    }
  154. 	}/*
  155. 	for(int i = 0;i<cntNodes;++i){
  156. 		cout<<reverseMap[i]<<" "<<(parent[i]>=0?reverseMap[parent[i]] : -1)<<endl;
  157. 		print(trieRoot[i]);
  158. 	}*/
  159. 	return 0;
  160. }
Success #stdin #stdout 0.02s 88632KB
comments (?)
stdin
copy 
6 4
1 2
5 1 3
2 1 4
3 2 5
4 2 1
6 3 3
1 4 2
6 0 12 0
7 12 7
4 0 7
stdout
copy 
0 6
2 7
0 1
https://ideone.com/n9fv7Y
language:
C++14 (gcc 8.3)
created:
285 days ago
visibility:
public

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!