#include <bits/stdc++.h>
using namespace std;
#define MAXQ 200200
int id[MAXQ];
vector<int> chi[MAXQ];
int t=1;
int val[MAXQ];
unordered_map<int, int> mp[MAXQ][32];
vector<pair<int, pair<int, int>>> qs[MAXQ];
int ans[MAXQ];
int sz[MAXQ];
int search(int t, int v, int tmp) {
int n=0;
int ans=0;
for(int i=31;i>=0;i--) {
int m=1<<i;
int c=v&m;
int nxt=n|(c^m);
auto p = mp[t][i].find(nxt);
if(p!=mp[t][i].end()&&p->second<=tmp) {
ans|=1<<i;
} else nxt=n|c;
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;
} else {
dfs2(bst);
id[v]=id[bst];
}
for(auto u : chi[v]) {
if(u==bst) continue;
dfs2(u);
for(int i=0;i<32;i++) {
for(auto pr : mp[id[u]][i]) {
auto p = mp[id[v]][i].find(pr.first);
if(p==mp[id[v]][i].end()) mp[id[v]][i].insert(pr);
else p->second=min(p->second, pr.second);
}
mp[id[u]][i].clear();
}
}
int n=0;
for(int i=31;i>=0;i--) {
n|=(val[v]&(1<<i));
mp[id[v]][i][n]=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... |