#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 = 30; 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>>(30*nodes, set<int>());
Node *root = new Node();
root->id = 1;
int ids = 1;
Node *now2 = root;
sets[now2->id].insert(1);
for (int i = 30; 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";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
529 ms |
150672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
