Submission #291245

#	Time	Username	Problem	Language	Result	Execution time	Memory
291245		penguinhacker	Klasika (COCI20_klasika)	C++17	66 / 110	4726 ms	47320 KiB

klasika

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

#define ll long long
#define ar array

const int MAXDIG=30;
struct Node {
	int nxt[2];
	Node() {nxt[0]=nxt[1]=-1;}
};
struct Trie {
	vector<Node> trie;
	Trie() {trie.emplace_back();}
	void add(int x) {
		int cur=0;
		for (int i=MAXDIG; ~i; --i) {
			int c=(x>>i)&1;
			if (trie[cur].nxt[c]==-1) {
				trie[cur].nxt[c]=trie.size();
				trie.emplace_back();
			}
			cur=trie[cur].nxt[c];
		}
	}

	int qry(int x) { //best xor in trie 
		int cur=0;
		int res=0;
		for (int i=MAXDIG; ~i; --i) {
			int c=(x>>i)&1;
			if (trie[cur].nxt[c^1]!=-1) {
				res+=(1<<i);
				cur=trie[cur].nxt[c^1];
			}
			else {
				cur=trie[cur].nxt[c];
			}
		}
		return res;
	}
} trie;

const int mxN=2e5;
int n=1, val[mxN];
vector<int> adj[mxN];

int dfs(int u, int x) {
	int MX=x^val[u];
	for (int v: adj[u]) {
		MX=max(MX, dfs(v, x));
	}
	return MX;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	trie.add(0);
	int q; cin >> q;
	while(q--) {
		string type; cin >> type;
		int a, b; cin >> a >> b;
		if (type=="Add") {
			--a;
			val[n]=val[a]^b;
			adj[a].push_back(n);
			trie.add(val[n]);
			++n;
		}
		if (type=="Query") {
			--a, --b;
			int ans=q<=2000?dfs(b, val[a]):trie.qry(val[a]);
			cout << ans << "\n";
		}
	}
	return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 33 / 33
• Subtask 4: 0 / 44