Submission #844936

#	Time	Username	Problem	Language	Result	Execution time	Memory
844936		serifefedartar	Klasika (COCI20_klasika)	C++17	33 / 110	1461 ms	524288 KiB

klasika

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 20;
const ll MAXN = 2e5 + 5;
 
vector<pair<int,pair<int,int>>> queries;
vector<vector<int>> graph;
vector<set<int>> sets;
vector<int> val;
int tin[MAXN], tout[MAXN];
 
struct Node {
	Node *to[2];
	int id;
	Node () {
		to[0] = NULL;
		to[1] = NULL;
	}
};
 
int T = 0;
void dfs(int node, int parent) {
	tin[node] = ++T;
	for (auto u : graph[node])
		dfs(u, node);
	tout[node] = T;
}
 
bool check(Node *node, int subtree) {
	int st = tin[subtree];
	int en = tout[subtree];
	auto u = sets[node->id].lower_bound(st);
	if (u == sets[node->id].end() || *u > en)
		return false;
	return true;
}
 
int solve(Node *node, int subtree, int val) {
	int ans = 0;
	for (int i = 31; i >= 0; i--) {
		bool bit = ((1<<i) & val) != 0;
		if (node->to[!bit] != NULL && check(node->to[!bit], subtree)) {
			ans += (1<<i);
			node = node->to[!bit];
		} else if (node->to[bit] != NULL && check(node->to[bit], subtree))
			node = node->to[bit];
		else
			return 0; 
	}
	return ans;
}
 
int main() {
	fast
	int Q;
	cin >> Q;
 
	queries = vector<pair<int,pair<int,int>>>(Q);
	graph = vector<vector<int>>(Q+5, vector<int>());
	val = vector<int>(Q+5, 0);
	int nodes = 1, a, b;
	string type;
	for (int i = 0; i < Q; i++) {
		cin >> type >> a >> b;
 
		if (type == "Add") {
			nodes++;
			val[nodes] = (val[a] ^ b);
			queries[i] = make_pair(1, make_pair(nodes, val[nodes]));
			graph[a].push_back(nodes);
		} else
			queries[i] = make_pair(0, make_pair(a, b));
	}
	dfs(1, 1);
 	
 	sets = vector<set<int>>(50*nodes, set<int>());
	Node *root = new Node();
	root->id = 1;
	int ids = 1;
	Node *now2 = root;
	sets[now2->id].insert(1);
	for (int i = 31; i >= 0; i--) {
				bool bit = 0;
				if (now2->to[bit] == NULL) {
					now2->to[bit] = new Node();
					now2->to[bit]->id = ++ids;
				}
				now2 = now2->to[bit];
				sets[now2->id].insert(1);
	}

	for (auto u : queries) {
		if (u.f) {
			Node *now = root;
			sets[now->id].insert(tin[u.s.f]);
			int x = u.s.s;
			for (int i = 31; i >= 0; i--) {
				bool bit = ((1<<i) & x) != 0;
				if (now->to[bit] == NULL) {
					now->to[bit] = new Node();
					now->to[bit]->id = ++ids;
				}
				now = now->to[bit];
				sets[now->id].insert(tin[u.s.f]);
			}
		} else {
			int node = u.s.f; 
			int subtree = u.s.s;
			Node *now = root;
			cout << solve(now, subtree, val[node]) << "\n";
		}
	}
}

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