Submission #291268

#	Time	Username	Problem	Language	Result	Execution time	Memory
291268		penguinhacker	Klasika (COCI20_klasika)	C++17	110 / 110	3059 ms	377464 KiB

klasika

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

#define ll long long
#define ar array

//#warning changenodes
const int MAXDIG=30, MXNODES=7e6;
struct Node {
	int nxt[2];
	set<int> pos;
	Node() {nxt[0]=nxt[1]=-1;}
};
struct Trie {
	vector<Node> trie;
	Trie() {trie.reserve(MXNODES); trie.emplace_back();}
	void add(int x, int p) {
		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];
			trie[cur].pos.insert(p);
		}
	}

	int qry(int x, int ql, int qr) { //best xor in trie 
		int cur=0;
		int res=0;
		for (int i=MAXDIG; ~i; --i) {
			int c=(x>>i)&1;
			int chk=trie[cur].nxt[c^1];
			bool can=chk!=-1;
			if (can) {
				auto it=trie[chk].pos.lower_bound(ql);
				if (it==trie[chk].pos.end()||*it>qr) can=0;
			}
			if (can) {
				res+=(1<<i);
				cur=chk;
			}
			else {
				cur=trie[cur].nxt[c];
			}
		}
		return res;
	}
} t;

const int mxN=2e5;
int n=1, q, val[mxN], which[mxN];
int tin[mxN], tout[mxN], timer=0;
ar<int, 3> queries[mxN];
vector<int> adj[mxN];

void dfs(int u=0) {
	tin[u]=timer++;
	for (int v : adj[u]) dfs(v);
	tout[u]=timer++;
}

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

	cin >> q;
	for (int i=0; i<q; ++i) {
		string s; cin >> s;
		int type=s=="Add"?1:2;
		int a, b; cin >> a >> b;
		if (type==1) {
			--a;
			adj[a].push_back(n);
			val[n]=val[a]^b;
			b=val[n];
			a=n++;
		}
		else --a, --b;
		queries[i]={type, a, b};
	}
	//for (int i=0; i<n; ++i) cout << val[i] << " ";
	dfs();
	t.add(0, 0);
	for (int i=0; i<q; ++i) {
		int a=queries[i][1], b=queries[i][2];
		if (queries[i][0]==1) {
			t.add(b, tin[a]);
		}
		else { //b
			int ans=t.qry(val[a], tin[b], tout[b]);
			cout << ans << "\n";
		}
	}
	/*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: 44 / 44