fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define endl '\n'
  4.  
  5. const int MAXN = 3e5+5;
  6. int trie[MAXN*32+1][2];//all values are <=2^31-1, and we need an additional root node
  7. int trieRoot[MAXN];
  8. int trieptr = 0;
  9. int add(int node, int value){
  10. 	memcpy(trie[++trieptr], trie[node], sizeof trie[0]);//copy root
  11. 	int cur = trieptr;
  12. 	int newRoot = cur;
  13. 	for(int p = 30; p>=0; --p){//all values are <=2^31-1
  14. 		int bit = (value >> p) &1;
  15. 		++trieptr;
  16. 		if(trie[cur][bit] > 0) memcpy(trie[trieptr], trie[trie[cur][bit]], sizeof trie[0]);//copy child
  17. 		trie[cur][bit] = trieptr;
  18. 		cur = trieptr;
  19. 	}
  20. 	return newRoot;
  21. }
  22. int search(int node, int value){
  23. 	int cur = node;
  24. 	int ans = 0;
  25. 	for(int p = 30; p>=0; --p){//all values are <=2^31-1
  26. 		int bit = (value >> p) &1;
  27. 		if(trie[cur][bit]>0){
  28. 			cur = trie[cur][bit];
  29. 			ans |= bit<<p;
  30. 		}else{
  31. 			cur = trie[cur][!bit];
  32. 			ans |= (!bit)<<p;
  33. 		}
  34. 	}
  35. 	return ans;
  36. }
  37.  
  38. int get_id(int x){
  39. 	static unordered_map<int,int> mp;
  40. 	if(!mp.count(x)) mp[x]=mp.size();
  41. 	return mp[x];
  42. }
  43.  
  44. int main() {
  45. 	ios::sync_with_stdio(false);
  46. 	cin.tie(0);
  47.  
  48. 	int N,Q,R, key;
  49. 	cin >> N >> Q;
  50. 	cin >> R >> key;
  51. 	R = get_id(R);
  52. 	trieRoot[R] = add(0,key);
  53.  
  54. 	for (int i = 0; i < N - 1; i++)
  55. 	{
  56. 		int u,v,k;
  57. 	    cin >> u >> v >> k;
  58. 	    u = get_id(u);
  59. 	    v = get_id(v);
  60. 		trieRoot[u] = add(trieRoot[v],k);
  61. 	}
  62.  
  63. 	int last_answer = 0;
  64.  
  65. 	for (int i = 0; i < Q; i++)
  66. 	{
  67. 		int t;
  68. 	    cin >> t;
  69.  
  70. 	    // find real value of t
  71. 	    t ^= last_answer;
  72.  
  73. 	    if (t == 0)
  74. 	    {
  75. 	    	int v,u,k;
  76. 	        cin >> v >> u >> k;
  77.  
  78. 	        // find real values for u, v, and k
  79. 	        u ^= last_answer;
  80. 	        v ^= last_answer;
  81. 	        k ^= last_answer;
  82. 	        //cout<<"Q: "<<t<<" "<<v<<" "<<u<<" "<<k<<endl;
  83. 	        u = get_id(u);
  84. 	        v = get_id(v);
  85. 	        trieRoot[u] = add(trieRoot[v],k);
  86. 	    }
  87. 	    else
  88. 	    {
  89. 	    	int v,k;
  90. 	        cin >> v >> k;
  91.  
  92. 	        // find real values for v, and k
  93. 	        v ^= last_answer;
  94. 	        k ^= last_answer;
  95.  
  96. 	        //cout<<"Q: "<<t<<" "<<v<<" "<<k<<endl;
  97.  
  98. 	        v = get_id(v);
  99.  
  100. 	        // compute the requested values
  101.  
  102. 	        int min_answer = k^search(trieRoot[v],k);//
  103. 	        int max_answer = k^search(trieRoot[v],~k);//
  104.  
  105. 	        cout<<min_answer<<" "<<max_answer<<endl;
  106.  
  107. 	        // update last_answer
  108. 	        last_answer = min_answer ^ max_answer;  
  109. 	    }
  110. 	}
  111. 	return 0;
  112. }
Success #stdin #stdout 0.01s 5284KB
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/ccrX5U
language:
C++14 (gcc 8.3)
created:
14 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!