oj.uz

Submission #476019

# Submission time Handle Problem Language Result Execution time Memory
476019 2021-09-24T15:28:21 Z KhaledFarhat Klasika (COCI20_klasika) C++14
0 / 110
 1008 ms 115520 KB 
#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;
	
	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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Incorrect 4 ms 5196 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Incorrect 4 ms 5196 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1008 ms 115520 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Incorrect 4 ms 5196 KB Output isn't correct
3 Halted 0 ms 0 KB -