Submission #446545

#	Time	Username	Problem	Language	Result	Execution time	Memory
446545		Arinoor	Klasika (COCI20_klasika)	C++17	110 / 110	1113 ms	105484 KiB

klasika

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
const int inf = 1e9 + 10;
const int maxlg = 31;

vector<pair<int, int>> query[maxn];
int ans_query[maxn];
vector<int> G[maxn];
int val[maxn], sz[maxn], adding_time[maxn];

struct Trie{
	struct node{
		node *child[2];
		int mini;
		int sz;

		node(){
			child[0] = nullptr;
			child[1] = nullptr;
			mini = inf;
			sz = 0;
		}

		node *getChild(bool bit){
			if(child[bit] == nullptr)
				child[bit] = new node();
			else if(child[bit]->sz == 0)
				child[bit]->mini = inf;
			return child[bit];
		}

		bool check(bool bit, int ind){
			if(child[bit] == nullptr or child[bit]->sz == 0)
				return false;
			return (child[bit]->mini) < ind;
		}

	};
	
	node *root;

	Trie(){
		root = new node();
	}

	void add(int v){
		node *cur = root;
		for(int i = maxlg - 1; i >= 0; i --){
			cur = cur->getChild(val[v] & (1 << i));
			cur->mini = min(cur->mini, adding_time[v]);
			cur->sz ++;
		}
	}

	void erase(int v){
		node *cur = root;
		for(int i = maxlg - 1; i >= 0; i --){
			cur = cur->getChild(val[v] & (1 << i));
			cur->sz --;
		}
	}

	int get(int a, int ind){
		node *cur = root;
		int ans = 0;
		for(int i = maxlg - 1; i >= 0; i --){
			bool bit = (a & (1 << i));
			if(cur->check(!bit, ind)){
				if(!bit)
					ans += (1 << i);
				cur = cur->child[!bit];
			}
			else{
				if(bit)
					ans += (1 << i);
				cur = cur->child[bit];
			}
		}
		return ans ^ a;
	}

} T;

void dfs_sz(int v){
	sz[v] = 1;
	for(int u : G[v]){
		dfs_sz(u);
		sz[v] += sz[u];
	}
}

void dfs_add(int v){
	T.add(v);
	for(int u : G[v])
		dfs_add(u);
}

void dfs_erase(int v){
	T.erase(v);
	for(int u : G[v]){
		dfs_erase(u);
	}
}

void dsu(int v, bool keep){
	int big_child = -1;
	int maxi = 0;
	for(int u : G[v]){
		if(sz[u] > maxi){
			maxi = sz[u];
			big_child = u;
		}
	}
	if(big_child == -1){
		for(auto q : query[v]){
			ans_query[q.second] = q.first ^ val[v];
		}
		if(keep)
			T.add(v);
		return;
	}
	for(int u : G[v]){
		if(u != big_child)
			dsu(u, false);
	}
	dsu(big_child, true);
	T.add(v);
	for(int u : G[v]){
		if(u != big_child){
			dfs_add(u);
		}
	}
	for(auto q : query[v]){
		ans_query[q.second] = T.get(q.first, q.second);
	}
	if(!keep){
		T.erase(v);
		for(int u : G[v]){
			dfs_erase(u);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int Q;
	cin >> Q;
	memset(ans_query, -1, sizeof ans_query);
	int vertex_cnt = 1;
	for(int i = 0; i < Q; i ++){
		string type;
		int x, y;
		cin >> type >> x >> y;
		if(type == "Add"){
			G[--x].push_back(vertex_cnt);
			val[vertex_cnt] = (y ^ val[x]);
			adding_time[vertex_cnt++] = i;
		}
		else{
			query[--y].push_back({val[--x], i});
		}
	}
	dfs_sz(0);
	dsu(0, 0);
	for(int i = 0; i < Q; i ++){
		if(ans_query[i] != -1){
			cout << ans_query[i] << '\n';
		}
	}
}

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