#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 {
struct node {
set<int> all;
int nt[2];
node(){
nt[0] = nt[1] = 0;
}
};
vector<node> t;
int cc;
trie() {
t.push_back({});
t.push_back({});
cc = 1;
}
vector<int> :: iterator it;
void add(int p, int x){
int v = 1;
for (int i = lg; i >= 0; i--){
bool bit = (x >> i) & 1;
if (!t[v].nt[bit]){
t[v].nt[bit] = ++cc;
t.push_back({});
}
v = t[v].nt[bit];
t[v].all.insert(p);
}
}
int get(int l, int r, int x){
int out = 0, v = 1;
for (int i = lg; i >= 0; i--){
bool bit = (x >> i) & 1;
int k = t[v].nt[!bit];
auto it = t[k].all.lower_bound(l);
if (it != t[k].all.end() && (*it) <= r){
v = k;
out += (1 << i);
continue;
}
v = t[v].nt[bit];
}
return out;
}
} t;
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);
t.add(1, 0);
for(int i = 1; i <= q; ++i) {
if(!op[i]) {
t.add(tin[qx[i]], dep[qx[i]]);
}
else {
int u = qx[i], v = qy[i];
cout << t.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 |
Incorrect |
2 ms |
5220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
5220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
366 ms |
65696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
5220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
