#include <bits/stdc++.h>
using namespace std;
#define MAXQ 200200
vector<int> trie[MAXQ][2];
vector<int> mn[MAXQ];
int id[MAXQ];
vector<int> chi[MAXQ];
int t=1;
int val[MAXQ];
vector<pair<int, pair<int, int>>> qs[MAXQ];
vector<pair<int, int>> vec[MAXQ];
int ans[MAXQ];
int sz[MAXQ];
void insert(int t, int v, int tmp) {
int n=0;
for(int i=31;i>=0;i--) {
int c=(v>>i)&1;
int nxt=trie[t][c][n];
if(!nxt) {
nxt=trie[t][c].size();
trie[t][c][n]=nxt;
mn[t].push_back(2e9);
trie[t][0].push_back(0);
trie[t][1].push_back(0);
}
mn[t][nxt]=min(mn[t][nxt], tmp);
n=nxt;
}
}
int search(int t, int v, int tmp) {
int n=0;
int ans=0;
for(int i=31;i>=0;i--) {
int c=(v>>i)&1;
int nxt=trie[t][c^1][n];
if(nxt&&mn[t][nxt]<=tmp) {
ans|=1<<i;
} else nxt=trie[t][c][n];
n=nxt;
}
return ans;
}
void dfs1(int v) {
sz[v]=1;
for(auto u : chi[v]) {
dfs1(u);
sz[v]+=sz[u];
}
}
void dfs2(int v) {
int bst=0;
for(auto u : chi[v]) {
if(sz[u]>sz[bst]) bst=u;
}
if(!bst) {
id[v]=v;
mn[v].push_back(v);
trie[v][0].push_back(0);
trie[v][1].push_back(0);
vec[v].push_back({v, val[v]});
} else {
dfs2(bst);
id[v]=id[bst];
}
for(auto u : chi[v]) {
if(u==bst) continue;
dfs2(u);
for(auto pr : vec[id[u]]) {
insert(id[v], pr.second, pr.first);
vec[id[v]].push_back(pr);
}
for(int i=0;i<2;i++) trie[id[u]][i].clear();
vec[id[u]].clear();
}
insert(id[v], val[v], v);
for(auto pr : qs[v]) {
int i=pr.first, vl=pr.second.first, t=pr.second.second;
ans[i]=search(id[v], vl, t);
}
}
int main() {
memset(ans, 0xff, sizeof(ans));
cin.tie(nullptr);
ios::sync_with_stdio(false);
val[1]=0;
int q;
cin >> q;
for(int i=0;i<q;i++) {
string op;
cin >> op;
if(op=="Add") {
int x, y;
cin >> x >> y;
++t;
chi[x].push_back(t);
val[t]=val[x]^y;
} else {
int a, b;
cin >> a >> b;
qs[b].push_back({i, {val[a], t}});
}
}
sz[0]=0;
dfs1(1);
dfs2(1);
for(int i=0;i<q;i++) {
int a=ans[i];
if(a>=0) cout << a << "\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |