oj.uz

Submission #844911

# Submission time Handle Problem Language Result Execution time Memory
844911 2023-09-06T08:44:51 Z serifefedartar Klasika (COCI20_klasika) C++17
0 / 110
 49 ms 23376 KB 
#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<int> val;
int tin[MAXN], tout[MAXN];
 
struct Node {
	Node *to[2];
	set<int> enter;
	Node() {
		enter = set<int>();
	}
};
 
int T = 0;
void dfs(int node, int parent) {
	tin[node] = ++T;
	for (auto u : graph[node]) {
		if (u == parent)
			continue;
		dfs(u, node);
	}
	tout[node] = T;
}
 
bool check(Node *node, int subtree) {
	int st = tin[subtree];
	int en = tout[subtree];
	auto u = node->enter.lower_bound(st);
	if (u == node->enter.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
			node = node->to[bit];
	}
	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;
	for (int i = 0; i < Q; i++) {
		string type;
		int a, b;
		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);
			graph[nodes].push_back(a);
		} else
			queries[i] = make_pair(0, make_pair(a, b));
	}
	dfs(1, 1);
 
	Node *root = new Node();
	for (auto u : queries) {
		if (u.f) {
			Node *now = root;
			now->enter.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 = now->to[bit];
				now->enter.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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 49 ms 23376 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -