#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
const int maxn = 2e5 + 5;
const int lg = 19;
int q;
int n;
int tin[maxn], tout[maxn], timer;
int op[maxn], qx[maxn], qy[maxn];
int par[maxn];
vector<pair<int, int>> g[maxn];
int dep[maxn], h[maxn];
void pre_dfs(int u) {
tin[u] = ++timer;
for(auto e:g[u]) {
int v = e.first, w = e.second;
dep[v] = dep[u] ^ w;
h[v] = h[u] + 1;
pre_dfs(v);
}
tout[u] = timer;
}
struct trie {
const static int lg = 30;
struct node {
node *child[2];
int cnt;
node() {
child[0] = child[1] = nullptr;
cnt = 0;
}
} *root;
trie() {
root = new node();
}
void add(int x) {
node *p = root;
for(int i = lg; i >= 0; --i) {
int c = (x >> i & 1);
if(p->child[c] == nullptr) {
p->child[c] = new node();
}
p = p->child[c];
p->cnt++;
}
}
int get(int x) {
node *p = root;
int ans = 0;
for(int i = lg; i >= 0; --i) {
int c = (x >> i & 1);
if(p->child[c ^ 1] and p->child[c ^ 1]->cnt) {
ans |= (1 << i);
p = p->child[c ^ 1];
}
else {
if(p->child[c] == nullptr) {
return ans;
}
p = p->child[c];
}
}
return ans;
}
};
struct segment_tree {
int n;
vector<trie> tree;
segment_tree() {}
segment_tree(int n) : n(n), tree(n * 4 + 6) {}
void update(int ind, int l, int r, int pos, int val) {
tree[ind].add(val);
if(l == r) {
return;
}
int mid = (l + r) >> 1;
if(pos <= mid) {
update(ind << 1, l, mid, pos, val);
}
else {
update(ind << 1 | 1, mid + 1, r, pos, val);
}
}
int get(int ind, int l, int r, int x, int y, int val) {
if(l > y || r < x) return 0;
if(x <= l and r <= y) {
return tree[ind].get(val);
}
int mid = (l + r) >> 1;
return max(get(ind << 1, l, mid, x, y, val), get(ind << 1 | 1, mid + 1, r, x, y, val));
}
void update(int pos, int val) {
update(1, 1, n, pos, val);
}
int get(int x, int y , int val) {
return get(1, 1, n, x, y, val);
}
} st;
void solve() {
cin >> q;
string s;
n = 1;
for(int i = 1; i <= q; ++i) {
cin >> s >> qx[i] >> qy[i];
if(s[0] == 'Q') {
op[i] = 1;
}
if(!op[i]) {
++n;
par[n] = qx[i];
g[qx[i]].push_back({n, qy[i]});
qx[i] = n;
}
}
pre_dfs(1);
st = segment_tree(n);
for(int i = 1; i <= q; ++i) {
if(!op[i]) {
st.update(tin[qx[i]], dep[qx[i]]);
}
else {
int u = qx[i], v = qy[i];
cout << st.get(tin[v], tout[v], dep[u]) << '\n';
}
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5464 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5464 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
682 ms |
500368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5464 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
