Submission #1285086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285086		vache_kocharyan	Klasika (COCI20_klasika)	C++20	110 / 110	2043 ms	523100 KiB

klasika

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <random>
#include <chrono>
#include <unordered_set>

using namespace std;

typedef long long ll;

#define UNIQUE_SORT(vec) do { \
	sort((vec).begin(), (vec).end()); \
	(vec).erase(unique((vec).begin(), (vec).end()), (vec).end()); \
} while(0)

#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define ss second
#define ff first
#define all(X) X.begin(), X.end()
#define rall(X) X.rbegin(), X.rend()
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define cinall(X) for(auto &i:X)cin >> i
#define printall(X) for(auto &i:X)cout << i

const int N = 2e5 + 5;
vector<int>G[N];
int xxor[N];

int t[N], tin[N], tout[N], a[N], b[N];

int timer = 0;

void dfs(int node, int parent)
{
	timer++;
	tin[node] = timer;
	for (auto i : G[node])
	{
		if (i == parent)continue;
		dfs(i, node);
	}
	timer++;
	tout[node] = timer;
}

int g[31 * N][2], root = 1, new_g = 1;
set<int>tins[26 * N];

struct Trie {
	inline void add(int x, int new_tin)
	{
		int cur_node = root;
		for (int i = 30; i >= 0; i--)
		{
			int bit = (x >> i) & 1;
			if (g[cur_node][bit] == 0)
			{
				g[cur_node][bit] = ++new_g;
			}
			tins[cur_node].insert(new_tin);
			cur_node = g[cur_node][bit];
		}
		tins[cur_node].insert(new_tin);
	}

	inline int query(long long x, int new_tin, int new_tout)
	{
		int cur_node = root, ans = 0;
		for (int i = 30; i >= 0; i--)
		{
			int bit = (x >> i) & 1;

			if (g[cur_node][1 - bit])
			{
				auto it = tins[g[cur_node][1 - bit]].lower_bound(new_tin);
				if (it != tins[g[cur_node][1 - bit]].end() && *it <= new_tout)
				{
					ans += (1 << i);
					cur_node = g[cur_node][1 - bit];
				}
				else
				{
					cur_node = g[cur_node][bit];
				}
			}
			else
			{
				cur_node = g[cur_node][bit];
			}
		}
		return ans;
	}
}trie;


void solve()
{
	int q;
	cin >> q;
	int ccnt = 1;
	for (int i = 1; i <= q; i++)
	{
		string s;
		cin >> s;

		if (s == "Add")
		{
			t[i] = 1;
			int x;
			int y;
			cin >> x >> y;

			ccnt++;
			
			a[i] = x;
			b[i] = ccnt;

			G[x].push_back(ccnt);
			xxor[ccnt] = xxor[x] ^ y;
		}
		else
		{
			cin >> a[i] >> b[i];
		}
	}

	dfs(1, 0);
	trie.add(0, tin[1]);

	for (int i = 1; i <= q; i++)
	{
		if (t[i] == 1)
		{
			trie.add(xxor[b[i]], tin[b[i]]);
		}
		else
		{
			cout << trie.query(xxor[a[i]], tin[b[i]], tout[b[i]]) << "\n";
		}
	}
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
		cout << endl;
	}
	return 0;
}

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