제출 #1265654

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1265654		goulthen	Klasika (COCI20_klasika)	C++20	110 / 110	2069 ms	442172 KiB

klasika

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

#define int long long
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second

const int MAXN = 2e5 + 10;
vector<pii> g[MAXN];
int a[MAXN], ti[MAXN], to[MAXN], t = 0;

struct Node {
	set<int> ids;
	Node *zero, *one;
	Node() {
		zero = one = NULL;
	}

} root;

void trie_add(Node *node, int bit, int val, int id) {
	node->ids.insert(id);
	if (bit < 0) return;
	if (val & (1 << bit)) {
		if (node->one == NULL) node->one = new Node();
		trie_add(node->one,bit-1,val,id);
	} else {
		if (node->zero == NULL) node->zero = new Node();
		trie_add(node->zero, bit-1, val, id);
	}
}

int trie_get(Node *node, int bit, int val, int from, int to) {
	if (bit < 0) return 0;

	if ((val&(1<<bit)) == 0) {
		if (node->one == NULL || node->one->ids.lower_bound(from) == node->one->ids.upper_bound(to)) {
			return trie_get(node->zero, bit-1,val, from, to);
		} else {
			return (1<<bit) + trie_get(node->one, bit - 1, val, from, to);
		}
	} else {
		if (node->zero == NULL || node->zero->ids.lower_bound(from) == node->zero->ids.upper_bound(to)) {
			return trie_get(node->one, bit - 1, val, from, to);
		} else {
			return (1<<bit) + trie_get(node->zero, bit-1,val, from, to);
		}
	}
}

void dfs(int u, int p = -1, int c = 0) {
	ti[u] = ++t;
	a[u] = c;
	for (auto &[v,w] : g[u]) {
		if (v==p) continue;
		dfs(v,u,c^w);
	}
	to[u] = t;
}

int32_t main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int q;cin >> q;
	vector<array<int,3>> qr;
	int n = 1;
	rep(i,2,q+1) {
		string tp;
		int x,y;cin >> tp >> x >> y;
		if (tp=="Add") {
			n++;
			g[n].pb({x,y});
			g[x].pb({n,y});
			qr.pb({1,n,0});
		} else {
			qr.pb({0,x,y});
		}
	}

	dfs(1);


	trie_add(&root, 30,0, ti[1]);
	for(auto &[tp,x,y] : qr) {
		if (tp) {
			trie_add(&root, 30, a[x], ti[x]);
		} else {
			cout << trie_get(&root, 30, a[x], ti[y], to[y]) << '\n';
		}
	}
	
	return 0;
}

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