Submission #291240

#	Time	Username	Problem	Language	Result	Execution time	Memory
291240		penguinhacker	Klasika (COCI20_klasika)	C++17	33 / 110	5063 ms	133160 KiB

klasika

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

#define ll long long
#define ar array

const int MAXDIG=30;
struct Node {
	int cnt=0;
	int nxt[2];
	Node() {nxt[0]=nxt[1]=-1;}
};
struct Trie {
	vector<Node> trie;
	Trie() {trie.emplace_back();}
	void reset() {trie.clear(); trie.emplace_back();}
	void add(int x) {
		int cur=0;
		++trie[0].cnt;
		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].cnt;
		}
	}

	/*void remove(int x) {
		int cur=0;
		--trie[0].cnt;
		for (int i=MAXDIG; ~i; --i) {
			int c=(x>>i)&1;
			assert(trie[cur].nxt[c]!=-1);
			cur=trie[cur].nxt[c];
			--trie[cur].cnt;
		}
	}*/

	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&&trie[trie[cur].nxt[c^1]].cnt>0) {
				res+=(1<<i);
				cur=trie[cur].nxt[c^1];
			}
			else {
				cur=trie[cur].nxt[c];
			}
		}
		return res;
	}
};

//try to rebuild every sqrt(n) queries, change block size to pass constraints
const int mxN=2e5;
int totNodes=1, n, val[mxN], parent[mxN];
int pos[mxN], iPos[mxN], sz[mxN], tin[mxN], tout[mxN];
bool vis[mxN];
vector<int> adj[mxN];
Trie tree[4*mxN];

void dfs(int u, int& ind, int& timer) {
	pos[u]=ind++;
	iPos[pos[u]]=u;
	tin[u]=timer++;
	sz[u]=1;
	for (int v : adj[u]) {
		dfs(v, ind, timer);
		sz[u]+=sz[v];
	}
	tout[u]=timer++;
}

void buildTree(int u=1, int l=0, int r=n-1) { //takes n*log(n)*31 time around
	tree[u].reset();
	for (int i=l; i<=r; ++i) {
		tree[u].add(val[iPos[i]]);
	}
	if (l==r) return;
	int mid=(l+r)/2;
	buildTree(2*u, l, mid), buildTree(2*u+1, mid+1, r);
}

int qry(int ql, int qr, int x, int u=1, int l=0, int r=n-1) { //take log(n)*31 time around
	if (l>qr||r<ql) return 0;
	if (ql<=l&&r<=qr) return tree[u].qry(x);
	int mid=(l+r)/2;
	return max(qry(ql, qr, x, 2*u, l, mid), qry(ql, qr, x, 2*u+1, mid+1, r));
}

vector<int> toCheck;
void rebuild() {
	n=totNodes;
	int ind=0, timer=0;
	dfs(0, ind, timer);
	buildTree();
	for (int i: toCheck) vis[i]=1;
	toCheck.clear();
}

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

int temp[mxN];

int dfs_check(int b, int x) {
	if (vis[x]) {
		return tin[b]<=tin[x]&&tout[b]>=tout[x];
	}
	return temp[x]=dfs_check(b, parent[x]);
}

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

	fill(temp, temp+mxN, -1);
	int q; cin >> q;
	while(q--) {
		string type; cin >> type;
		int a, b; cin >> a >> b;
		if (type=="Add") {
			--a;
			val[totNodes]=val[a]^b;
			adj[a].push_back(totNodes);
			parent[totNodes]=a;
			toCheck.push_back(totNodes);
			++totNodes;
			//rebuild();
			if (totNodes%2000==0) rebuild();
		}
		if (type=="Query") {
			--a, --b;
			int ans=0;
			if (vis[b]) {
				int l=pos[b], r=pos[b]+sz[b]-1;
				ans=qry(l, r, val[a]);
				for (int i: toCheck) {
					if (temp[i]==-1) dfs_check(b, i);
					if (temp[i]) {
						ans=max(ans, val[i]^val[a]);
					}
				}
				for (int i: toCheck) temp[i]=-1;
			}
			else {
				ans=brute(b, val[a]);
			}
			cout << ans << "\n";
			//cout << "testing\n";
		}
	}
	return 0;
}

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