Submission #1093040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093040		Hacv16	Klasika (COCI20_klasika)	C++17	33 / 110	698 ms	524288 KiB

klasika

#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native")
 
const int MAX = 3e5 + 15;
const int LOG = 31;
 
int n = 1, q, x[MAX];
int timer, tin[MAX], tout[MAX];
 
vector<int> adj[MAX];
 
struct Trie
{
	int numNodes;
	vector<array<int, 2>> trie;
 
	int create()
	{
		trie.push_back({ 0, 0 });
		return numNodes++;
	}
 
	Trie(void){ numNodes = 0; create(); }
 
	void add(int x)
	{
		int cur = 0;
 
		for(int i = LOG - 1; i >= 0; i--)
		{
			bool id = (x & (1 << i));
 
			if(trie[cur][id] == 0)
			{
				int newNode = create();
				trie[cur][id] = newNode;
			}
 
			cur = trie[cur][id];
		}
	}
 
	int query(int x)
	{
		int cur = 0, resp = 0;
 
		for(int i = LOG - 1; i >= 0; i--)
		{
			bool id = (x & (1 << i));
 
			if(trie[cur][!id] != 0)
			{
				resp ^= (1 << i);
				cur = trie[cur][!id];
 
			} else cur = trie[cur][id];
		}
 
		return resp;
	}

} seg[4 * MAX];
 
void build(int p, int l, int r)
{
	seg[p] = Trie();

	if(l == r) return;

	int m = (l + r) >> 1, e = 2 * p, d = e + 1; 
	build(e, l, m); build(d, m + 1, r);
}

void dfs(int u, int p)
{
	tin[u] = ++timer;
 
	for(auto v : adj[u])
	{
		if(v == p) continue;
		dfs(v, u);
	}
 
	tout[u] = timer;
}
 
void update(int i, int val, int p, int l, int r)
{
    if(i < l || i > r) return;
    if(l == r)
    {
        seg[p].add(val); 
        return;
    }
    
    int m = (l + r) >> 1, e = 2 * p, d = e + 1;
    update(i, val, e, l, m); update(i, val, d, m + 1, r);
    
    seg[p].add(val);
}
 
int query(int a, int b, int val, int p, int l, int r)
{
	if(a > r || b < l) return -1;
	if(a <= l && r <= b) return seg[p].query(val);
 
	int m = (l + r) >> 1, e = 2 * p, d = e + 1;
	return max(query(a, b, val, e, l, m), query(a, b, val, d, m + 1, r));
}
 
int32_t main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
 
	cin >> q;
 
	vector<tuple<int, int, int>> events;
 
	events.emplace_back(1, 1, x[1]);
 
	while(q--)
	{
		string op; cin >> op;
 
		if(op == "Add")
		{
			int p, w; cin >> p >> w;
			int newNode = ++n;
 
			x[newNode] = x[p] ^ w;
 
			adj[p].push_back(newNode);
			adj[newNode].push_back(p);
 
			events.emplace_back(1, newNode, x[newNode]);
 
		}else{
			int a, b; cin >> a >> b;
			events.emplace_back(2, x[a], b);
		}
	}
 
	dfs(1, 1);
	build(1, 1, n);
 
	for(auto [type, x, y] : events)
	{
		if(type == 1) update(tin[x], y, 1, 1, n);
		else cout << query(tin[y], tout[y], x, 1, 1, n) << '\n';
	}
 
	cout << '\n';
}

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