oj.uz

Submission #1093015

# Submission time Handle Problem Language Result Execution time Memory
1093015 2024-09-25T17:36:15 Z Hacv16 Klasika (COCI20_klasika) C++17
33 / 110
 111 ms 38116 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 12736 KB Output is correct
2 Correct 99 ms 21300 KB Output is correct
3 Correct 96 ms 19892 KB Output is correct
4 Correct 102 ms 38116 KB Output is correct
5 Correct 88 ms 12656 KB Output is correct
6 Correct 98 ms 21320 KB Output is correct
7 Correct 102 ms 19892 KB Output is correct
8 Correct 111 ms 37792 KB Output is correct
9 Correct 88 ms 12868 KB Output is correct
10 Correct 96 ms 21152 KB Output is correct
11 Correct 92 ms 19900 KB Output is correct
12 Correct 104 ms 37976 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -