Submission #855909

#	Time	Username	Problem	Language	Result	Execution time	Memory
855909		wakandaaa	Klasika (COCI20_klasika)	C++17	110 / 110	2069 ms	435380 KiB

klasika

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

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 520
#endif

const int N = 2e5 + 5;
const int MOD = 1e9 + 7; // 998244353
const int inf = INT_MAX; // LLONG_MAX
const int LOG = 30;
template<class T> bool minimize(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool maximize(T &a, T b) { return a < b ? (a = b, true) : false; }
template<class T> bool add(T &a, T b) { a += b; while (a > MOD) a -= MOD; return true; }

#define BIT(x, i) (((x) >> (i)) & 1)

struct TrieNode {
	set<int> s;
	TrieNode *child[2];
	TrieNode() {
		child[0] = child[1] = NULL;
	}
};

struct Trie {
	TrieNode *root;
	Trie() {
		root = new TrieNode();
	}
	void add(int value, int id) {
		TrieNode *p = root;
		for (int i = LOG; i >= 0; --i) {
			int c = BIT(value, i);
			if (p->child[c] == NULL) p->child[c] = new TrieNode();
			p = p->child[c];
			p->s.insert(id);
		}
	}
	int get(int value, int L, int R) {
		int ans = 0;
		TrieNode *p = root;
		for (int i = LOG; i >= 0; --i) {
			int c = BIT(value, i);
			c ^= 1;
			if (p->child[c] == NULL || p->child[c]->s.lower_bound(L) == p->child[c]->s.upper_bound(R)) p = p->child[c ^ 1];
			else {
				ans += (1 << i);
				p = p->child[c];
			}
		}
		return ans;
	}
} trie;

struct Query {
	int type, x, y;
};

vector<pair<int, int> > g[N];
int St[N], Ft[N], Rxor[N];
vector<Query> Q;
int Time = 0;

void DFS(int u, int p, int L) {
	St[u] = ++Time;
	Rxor[u] = L;
	for (auto [v, w] : g[u]) if (v != p) {
		DFS(v, u, w ^ L);
	}
	Ft[u] = Time;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n = 1;
	int q; cin >> q;
	while (q--) {
		string s; cin >> s;
		int x, y; cin >> x >> y;
		--x;
		if (s == "Add") {
			Q.push_back({0, n, y});
			g[x].push_back({n, y});
			g[n].push_back({x, y});
			++n;
		} else {
			--y;
			Q.push_back({1, x, y});
		}
	}

	DFS(0, -1, 0);
	trie.add(0, St[0]);

	for (auto [type, x, y] : Q) {
		if (type == 0) trie.add(Rxor[x], St[x]);
		else cout << trie.get(Rxor[x], St[y], Ft[y]) << '\n';
	}

	return 0;
}
// I'm thinking out loud!

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