Submission #476029

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
476029	2021-09-24T16:01:49 Z	KhaledFarhat	Klasika (COCI20_klasika)	C++14	110 / 110	2922 ms	471308 KB

klasika

#include <bits/stdc++.h>
using namespace std;

struct TrieNode {
	TrieNode() {
		memset(child, 0, sizeof child);
	}
	
	int child[2];
	set<int> times;
};

struct Trie {
	Trie() {
		fetchNode();
		root = fetchNode();
	}
	
	void insert(int number, int inTime) {
		int current = root;
		
		for (int bit = 30; bit >= 0; --bit) {
			bool value = number & (1 << bit);
			
			if (nodes[current].child[value] == 0) {
				int index = fetchNode();
				nodes[current].child[value] = index;
			}
			
			current = nodes[current].child[value];
			nodes[current].times.insert(inTime);
		}
	}
	
	int getMaxXor(int number, int L, int R) {
		int maxXor = 0;
		int current = root;
		
		for (int bit = 30; bit >= 0; --bit) {
			bool value = number & (1 << bit);
			
			vector<int> child = {nodes[current].child[0], nodes[current].child[1]};
			
			if (child[!value] != 0) {
				auto it = nodes[child[!value]].times.lower_bound(L);
				
				if (it != nodes[child[!value]].times.end() && (*it) <= R) {
					current = child[!value];
					maxXor |= 1 << bit;
					continue;
				}
			}
			
			current = child[value];
		}
		
		return maxXor;
	}
	
	int fetchNode() {
		nodes.push_back(TrieNode());
		
		return (int)nodes.size() - 1;
	}
	
	int root;
	vector<TrieNode> nodes;
};

const int MAX = 2e5 + 9;
const int ROOT = 1;
int n, pathFromRoot[MAX];
int inTime[MAX], outTime[MAX], dfsCounter;
vector<int> adj[MAX];

void Dfs(int node) {
	++dfsCounter;
	inTime[node] = dfsCounter;
	
	for (int child : adj[node]) {
		Dfs(child);
	}
	
	outTime[node] = dfsCounter;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int q;
	cin >> q;
		
	vector<pair<int, int>> queries(q);	
	n = 1;
	
	for (int i = 0; i < q; ++i) {
		string query;
		cin >> query;
		
		if (query == "Add") {
			int x, y;
			cin >> x >> y;
			
			int node = ++n;
			pathFromRoot[node] = pathFromRoot[x] ^ y;
			adj[x].push_back(node);
			
			queries[i] = {node, 0};
		}
		else {
			int a, b;
			cin >> a >> b;
			
			queries[i] = {a, b};
		}
	}
	
	Dfs(ROOT);
	Trie trie;
	
	trie.insert(pathFromRoot[ROOT], inTime[ROOT]);
	
	for (int i = 0; i < q; ++i) {
		if (queries[i].second == 0) {
			int node = queries[i].first;
			
			trie.insert(pathFromRoot[node], inTime[node]);
		}
		else {
			int from = queries[i].first;
			int to = queries[i].second;
			
			cout << trie.getMaxXor(pathFromRoot[from], inTime[to], outTime[to]) << "\n";
		}
	}
	
	return 0;
}

Subtask #1
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	5196 KB	Output is correct
2	Correct	3 ms	5196 KB	Output is correct
3	Correct	3 ms	5324 KB	Output is correct
4	Correct	3 ms	5400 KB	Output is correct
5	Correct	3 ms	5068 KB	Output is correct
6	Correct	4 ms	5148 KB	Output is correct
7	Correct	4 ms	5324 KB	Output is correct
8	Correct	3 ms	5452 KB	Output is correct
9	Correct	4 ms	5196 KB	Output is correct
10	Correct	3 ms	5324 KB	Output is correct
11	Correct	3 ms	5452 KB	Output is correct
12	Correct	4 ms	5452 KB	Output is correct

Subtask #2
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	5196 KB	Output is correct
2	Correct	3 ms	5196 KB	Output is correct
3	Correct	3 ms	5324 KB	Output is correct
4	Correct	3 ms	5400 KB	Output is correct
5	Correct	3 ms	5068 KB	Output is correct
6	Correct	4 ms	5148 KB	Output is correct
7	Correct	4 ms	5324 KB	Output is correct
8	Correct	3 ms	5452 KB	Output is correct
9	Correct	4 ms	5196 KB	Output is correct
10	Correct	3 ms	5324 KB	Output is correct
11	Correct	3 ms	5452 KB	Output is correct
12	Correct	4 ms	5452 KB	Output is correct
13	Correct	8 ms	6504 KB	Output is correct
14	Correct	9 ms	8060 KB	Output is correct
15	Correct	10 ms	8352 KB	Output is correct
16	Correct	11 ms	11040 KB	Output is correct
17	Correct	7 ms	6504 KB	Output is correct
18	Correct	9 ms	8012 KB	Output is correct
19	Correct	10 ms	8184 KB	Output is correct
20	Correct	11 ms	9208 KB	Output is correct
21	Correct	9 ms	6456 KB	Output is correct
22	Correct	10 ms	7984 KB	Output is correct
23	Correct	10 ms	8192 KB	Output is correct
24	Correct	12 ms	9248 KB	Output is correct

Subtask #3
33.0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1008 ms	115584 KB	Output is correct
2	Correct	1479 ms	233028 KB	Output is correct
3	Correct	2072 ms	286380 KB	Output is correct
4	Correct	2643 ms	471156 KB	Output is correct
5	Correct	1024 ms	116696 KB	Output is correct
6	Correct	1604 ms	229716 KB	Output is correct
7	Correct	2178 ms	282188 KB	Output is correct
8	Correct	2736 ms	464468 KB	Output is correct
9	Correct	883 ms	117056 KB	Output is correct
10	Correct	1506 ms	230356 KB	Output is correct
11	Correct	2021 ms	284280 KB	Output is correct
12	Correct	2683 ms	465928 KB	Output is correct

Subtask #4
44.0 / 44.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	5196 KB	Output is correct
2	Correct	3 ms	5196 KB	Output is correct
3	Correct	3 ms	5324 KB	Output is correct
4	Correct	3 ms	5400 KB	Output is correct
5	Correct	3 ms	5068 KB	Output is correct
6	Correct	4 ms	5148 KB	Output is correct
7	Correct	4 ms	5324 KB	Output is correct
8	Correct	3 ms	5452 KB	Output is correct
9	Correct	4 ms	5196 KB	Output is correct
10	Correct	3 ms	5324 KB	Output is correct
11	Correct	3 ms	5452 KB	Output is correct
12	Correct	4 ms	5452 KB	Output is correct
13	Correct	8 ms	6504 KB	Output is correct
14	Correct	9 ms	8060 KB	Output is correct
15	Correct	10 ms	8352 KB	Output is correct
16	Correct	11 ms	11040 KB	Output is correct
17	Correct	7 ms	6504 KB	Output is correct
18	Correct	9 ms	8012 KB	Output is correct
19	Correct	10 ms	8184 KB	Output is correct
20	Correct	11 ms	9208 KB	Output is correct
21	Correct	9 ms	6456 KB	Output is correct
22	Correct	10 ms	7984 KB	Output is correct
23	Correct	10 ms	8192 KB	Output is correct
24	Correct	12 ms	9248 KB	Output is correct
25	Correct	1008 ms	115584 KB	Output is correct
26	Correct	1479 ms	233028 KB	Output is correct
27	Correct	2072 ms	286380 KB	Output is correct
28	Correct	2643 ms	471156 KB	Output is correct
29	Correct	1024 ms	116696 KB	Output is correct
30	Correct	1604 ms	229716 KB	Output is correct
31	Correct	2178 ms	282188 KB	Output is correct
32	Correct	2736 ms	464468 KB	Output is correct
33	Correct	883 ms	117056 KB	Output is correct
34	Correct	1506 ms	230356 KB	Output is correct
35	Correct	2021 ms	284280 KB	Output is correct
36	Correct	2683 ms	465928 KB	Output is correct
37	Correct	1466 ms	119044 KB	Output is correct
38	Correct	1998 ms	233380 KB	Output is correct
39	Correct	2398 ms	288704 KB	Output is correct
40	Correct	2736 ms	471308 KB	Output is correct
41	Correct	1618 ms	117160 KB	Output is correct
42	Correct	2140 ms	230076 KB	Output is correct
43	Correct	2582 ms	282492 KB	Output is correct
44	Correct	2922 ms	464800 KB	Output is correct
45	Correct	1551 ms	117536 KB	Output is correct
46	Correct	2210 ms	230908 KB	Output is correct
47	Correct	2552 ms	283108 KB	Output is correct
48	Correct	2818 ms	466076 KB	Output is correct

Submission #476029

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 22.0 / 22.0

Subtask #3 33.0 / 33.0

Subtask #4 44.0 / 44.0

Subtask #1
11.0 / 11.0

Subtask #2
22.0 / 22.0

Subtask #3
33.0 / 33.0

Subtask #4
44.0 / 44.0