This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,q;
vector<tuple<int,int,int>> qr;
int val[N];
vector<int> adj[N];
int tin[N],tout[N],pos[N];
int timer=0;
set<int> alive;
struct Trie{
struct Node;
using Ptr = Node*;
struct Node{
int cnt;
array<Ptr,2> ch;
Node():cnt(0),ch{nullptr,nullptr}{}
};
Ptr root[N];
Ptr clone(Ptr o){
if(o)return new Node(*o);
else return new Node();
}
int get_cnt(Ptr t){
return t?t->cnt:0;
}
Ptr get_ch(Ptr t,int i){
return t?t->ch[i]:nullptr;
}
Ptr update(Ptr o,int x){
Ptr rt=clone(o);
Ptr u=rt;
u->cnt++;
for(int i=29;i>=0;i--){
int c=x>>i&1;
u->ch[c]=clone(o=get_ch(o,c));
u=u->ch[c];
u->cnt++;
}
return rt;
}
int query(Ptr tl,Ptr tr,int x){
int res=0;
for(int i=29;i>=0;i--){
int c=x>>i&1;
if(get_cnt(get_ch(tr,c^1))-get_cnt(get_ch(tl,c^1))){
tl=get_ch(tl,c^1);
tr=get_ch(tr,c^1);
res|=1<<i;
}else{
tl=get_ch(tl,c);
tr=get_ch(tr,c);
}
}
return res;
}
}tr;
void dfs(int u){
tin[u]=++timer;
pos[timer]=u;
for(auto v:adj[u]){
dfs(v);
}
tout[u]=timer;
}
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin >> q;
qr.resize(q);
n=1;
for(auto &[o,x,y]:qr){
string op;
cin >> op >> x >> y;
if(op=="Add"){
o=0;
val[++n]=val[x]^y;
adj[x].emplace_back(n);
x=n;
}else{
o=1;
}
}
dfs(1);
tr.root[0]=nullptr;
for(int i=1;i<=n;i++){
tr.root[i]=tr.update(tr.root[i-1],val[pos[i]]);
}
for(auto &[o,x,y]:qr){
if(o==0){
alive.emplace(tin[x]);
}else{
int l=tin[y];
int r=*prev(alive.upper_bound(tout[y]));
cout << tr.query(tr.root[l-1],tr.root[r],val[x]) << "\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... |