Submission #1163731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163731		nhq0914	Klasika (COCI20_klasika)	C++17	110 / 110	337 ms	148456 KiB

klasika

#define ll long long
#define ull unsigned long long
#include <bits/stdc++.h>
#define isz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define RF(name) if(fopen(name".INP", "r")) {freopen(name".INP", "r", stdin); freopen(name".INP", "w", stdout);}
using namespace std;

const int MaxN = 2e5 + 1;

int q, Tsize = 1, xorTo[MaxN], ans[MaxN];

vector <int> g[MaxN];
vector <pair <int, int>> queries[MaxN];

struct node {
	int child[2], intime, val;
	node() {
		child[0] = child[1] = 0;
		intime = 2e9;
		val = -1;
	}
};

struct {
	vector <int> rootNodes;
	vector <node> T;

	void add_root() {
		rootNodes.push_back(isz(T));
		T.push_back(node());
	}

	void add(const int &n, int rootn, int cur_time) {
		--rootn;
		int p = rootNodes[rootn];
		for(int i = 30; ~i; --i) {
			bool t = (n >> i) & 1;
			if(!T[p].child[t]) {
				T[p].child[t] = isz(T);
				T.push_back(node());
			}
			p = T[p].child[t];
			T[p].intime = min(T[p].intime, cur_time);
		}
		T[p].val = n;
	}

	int max_xor(const int &n, int rootn, int cur_time) {
		--rootn;
		int p = rootNodes[rootn];
		for(int i = 30; ~i; --i) {
			bool t = (n >> i) & 1;
			if(T[p].child[!t] && T[T[p].child[!t]].intime <= cur_time) {
				p = T[p].child[!t];
			}
			else if(T[p].child[t] && T[T[p].child[t]].intime <= cur_time) {
				p = T[p].child[t];
			}
		}
		return n ^ T[p].val;
	}
} trie;

void dfs_merge(int p1, int p2, int cur_bit) {
	if(p1 == p2) return;
	for(int i = 0; i < 2; ++i) if(trie.T[p2].child[i]) {
		if(!trie.T[p1].child[i]) {
			trie.T[p1].child[i] = trie.T[p2].child[i];
		}
		trie.T[trie.T[p1].child[i]].intime = min(trie.T[trie.T[p1].child[i]].intime, trie.T[trie.T[p2].child[i]].intime);
		if(cur_bit) dfs_merge(trie.T[p1].child[i], trie.T[p2].child[i], cur_bit - 1);
	}
}

void dfs(int v) {
	for(int &x: g[v]) {
		dfs(x);
		dfs_merge(trie.rootNodes[v - 1], trie.rootNodes[x - 1], 30);
	}
	for(pair <int, int> &x: queries[v]) {
		int &xor_val = x.first, &i = x.second;
		ans[i] = trie.max_xor(xor_val, v, i);
	}
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	
	memset(ans, -1, sizeof ans);

	cin >> q;
	trie.add_root();
	trie.add(0, 1, -1);
	for(int x, y, i = 0; i < q; ++i) {
		string t; cin >> t >> x >> y;
		if(t == "Add") {
			++Tsize;
			xorTo[Tsize] = xorTo[x] ^ y;
			g[x].push_back(Tsize);
			trie.add_root();
			trie.add(xorTo[Tsize], Tsize, i);
		}
		else {
			queries[y].push_back({xorTo[x], i});
		}
	}
	dfs(1);
	for(int i = 0; i < q; ++i) if(ans[i] >= 0) cout << ans[i] << '\n';

	return 0;
}

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