fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 2e5 + 5; 
  12. const int Q = 2e5 + 5; 
  13.  
  14. struct Query {
  15. 	int type, u, v; 
  16. }; 
  17.  
  18. int n, q;  
  19. vector<int> adj[N]; 
  20. vector<Query> queries;  
  21.  
  22. int dist[N]; // dist[u] = Tổng xor của đường đi từ 1 (gốc) đến u 
  23. int tin[N], tout[N], timer;  
  24.  
  25. void dfs(int u, int p) {
  26. 	tin[u] = ++timer;  
  27. 	for (int v : adj[u]) {
  28. 		if (v == p) continue;  
  29. 		dfs(v, u); 
  30. 	}
  31. 	tout[u] = timer; 
  32. }
  33.  
  34. struct Trie {
  35. 	struct Node {
  36. 		int nxt[2];  
  37. 		set<int> s;  
  38.  
  39. 		Node() {
  40. 			memset(nxt, 0, sizeof nxt); 
  41. 		}
  42. 	};
  43.  
  44. 	vector<Node> t;  
  45.  
  46. 	Trie() {
  47. 		t = vector<Node>(1); 
  48. 	}
  49.  
  50. 	void add(int x) {
  51. 		int v = 0;  
  52. 		for (int i = 30; i >= 0; i--) {
  53. 			int c = (dist[x] >> i) & 1; 
  54. 			if (t[v].nxt[c] == 0) {
  55. 				t[v].nxt[c] = t.size(); 
  56. 				t.push_back(Node()); 
  57. 			}
  58. 			v = t[v].nxt[c];
  59. 			t[v].s.insert(tin[x]);  
  60. 		}
  61. 	}
  62.  
  63. 	int getMaxXor(int x, int y) {
  64. 		int v = 0;  
  65. 		int ans = 0;  
  66. 		for (int i = 30; i >= 0; i--) {
  67. 			int c = (dist[x] >> i) & 1; 
  68. 			int nxt_v0 = t[v].nxt[c], nxt_v1 = t[v].nxt[c ^ 1];  
  69. 			auto it = t[nxt_v1].s.lower_bound(tin[y]); 
  70. 			if (it != t[nxt_v1].s.end() && (*it) <= tout[y]) {
  71. 				ans |= (1 << i);  
  72. 				v = nxt_v1; 
  73. 			}	
  74. 			else {
  75. 				v = nxt_v0; 
  76. 			}
  77. 		}
  78. 		return ans; 
  79. 	}
  80. }; 
  81.  
  82. // - Bài toán con: Làm sao để tính nhanh tổng xor của đường đi từ u đến v (với u, v là hai đỉnh bất kì trên cây)
  83. // - Đáp án: dist[u] ^ dist[v] với dist[u], dist[v] là tổng xor của đường đi từ gốc đến u, v 
  84.  
  85. // - Bài này ta có thể tiếp cận theo 2 cách là dùng Small to Large hoặc Euler Tour
  86. // - Đối với sol sử dụng Euler Tour thì đầu tiên ta cần tính được tin[], tout[] của cây tạo được sau cả Q truy vấn, sau đó duyệt qua lại Q truy vấn để trả lời
  87. // - Với truy vấn Query u v thì ta cần tìm đỉnh w trong đoạn [tin(v), tout(v)] sao cho dist[u] ^ dist[w] là lớn nhất
  88. // => Có thể giải quyết bằng Trie
  89. // - Quan trọng là làm sao để check có đi được sang 1 trong 2 bên nhánh trong lúc tính đáp án
  90. // => Đi được khi bên nhánh đó có tồn tại đỉnh w sao cho tin(w) thuộc đoạn [tin(v), tout(v)]
  91. // => Mỗi nút trên cây Trie có thêm 1 CTDL set để lưu tin() của những đỉnh đi qua nó trong lúc thêm vào Trie
  92. //    Lúc check ta chỉ cần dùng lower_bound/upper_bound trên set 
  93. // Độ phức tạp: O(q * 31 * log2(n) * C), có thể chạy chậm hơn do tốn nhiều bộ nhớ nhưng vẫn vừa đủ để pass bài này
  94.  
  95. int main() {
  96. 	ios::sync_with_stdio(false); 
  97. 	cin.tie(nullptr); 	
  98. 	cin >> q; 
  99.  
  100. 	n = 1;
  101. 	dist[1] = 0;    
  102. 	for (int i = 0; i < q; i++) {
  103. 		string type; cin >> type; 
  104. 		if (type == "Add") {
  105. 			int p, val; 
  106. 			cin >> p >> val;  
  107. 			int u = ++n;   
  108. 			adj[p].push_back(u);  
  109. 			adj[u].push_back(p); 
  110. 			dist[u] = dist[p] ^ val;
  111. 			queries.push_back({1, u});  
  112. 		}
  113. 		else {
  114. 			int u, v; 
  115. 			cin >> u >> v;  
  116. 			queries.push_back({2, u, v}); 
  117. 		}
  118. 	}
  119.  
  120. 	timer = 0;  
  121. 	dfs(1, -1);
  122.  
  123. 	Trie trie;  
  124. 	trie.add(1);
  125. 	for (int i = 0; i < q; i++) {
  126. 		int type = queries[i].type; 
  127. 		int u = queries[i].u;  
  128. 		if (type == 1) {
  129. 			trie.add(u); 
  130. 		}
  131. 		else {
  132. 			int v = queries[i].v;  
  133. 			int ans = trie.getMaxXor(u, v); 
  134. 			cout << ans << '\n'; 
  135. 		}
  136. 	}
  137. }
Success #stdin #stdout 0.01s 9636KB
comments (?)
stdin
copy 
4
Add 1 5
Query 1 1
Add 1 7
Query 1 1
stdout
copy 
5
7
https://ideone.com/rKX1o0
language:
C++14 (gcc 8.3)
created:
179 days 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!