Submission #1093015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093015		Hacv16	Klasika (COCI20_klasika)	C++17	33 / 110	111 ms	38116 KiB

klasika

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

const int MAX = 2e5 + 15;
const int LOG = 31;

int n = 1, q, x[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;
	}
};

int32_t main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> q;

	Trie T = Trie();
	T.add(x[1]);

	while(q--)
	{
		string op; cin >> op;

		if(op == "Add")
		{
			int p, w; cin >> p >> w;
			x[++n] = x[p] ^ w;

			T.add(x[n]);

		}else{
			int a, b; cin >> a >> b;
			// assert(b == 1);

			cout << T.query(x[a]) << '\n';
		}
	}
}

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