#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=2e5;
//const int L=30;
const int L=3;
struct Trie
{
int mn_time;
Trie *e[2];
};
const int TRIE_SIZE=N*(L+1)+10;
Trie triemem[TRIE_SIZE];
int trieit=0;
Trie* newtrie()
{
return &triemem[trieit++];
}
int getmn_time(Trie* x)
{
return (x==nullptr ? N+10:x->mn_time);
}
Trie* build(int c,int t,int l)
{
Trie* rt=newtrie();
rt->mn_time=t;
if(l<0)
return rt;
bool tmp=(c&(1<<l));
//cerr<<tmp<<" "<<c<<"\n";
rt->e[tmp]=build(c,t,l-1);
return rt;
}
Trie* merge(Trie* x,Trie* y)
{
if(x==nullptr)
return y;
if(y==nullptr)
return x;
x->mn_time=min(x->mn_time,y->mn_time);
for(int i:{0,1})
{
//cerr<<i<<" "<<getmn_time(x->e[i])<<" "<<getmn_time(y->e[i])<<"\n";
x->e[i]=merge(x->e[i],y->e[i]);
}
return x;
}
int read(Trie* x,int c,int t,int l)
{
if(l==-1)
return c;
bool tmp=(c&(1<<l));
//cerr<<c<<" "<<t<<" "<<l<<" "<<tmp<<"\n";
c|=(1<<l);
if(getmn_time(x->e[!tmp])<t)
return read(x->e[!tmp],c,t,l-1);
c^=(1<<l);
return read(x->e[tmp],c,t,l-1);
}
vector<pair<int,int>> que[N+10];
int tim[N+10];
vector<int> e[N+10];
int d[N+10];
int ans[N+10];
bool is_query[N+10];
Trie* dfs(int x)
{
Trie* rt=build(d[x],tim[x],L);
for(auto v:e[x])
{
auto tmp=dfs(v);
rt=merge(rt,tmp);
}
for(auto [t,c]:que[x])
ans[t]=read(rt,c,t,L);
return rt;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int q,n=1;
cin>>q;
for(int i=1;i<=q;i++)
{
string t;
int a,b;
cin>>t>>a>>b;
if(t=="Add")
{
e[a].push_back(++n);
d[n]=d[a]^b;
tim[n]=i;
}
else
{
is_query[i]=true;
que[b].emplace_back(i,d[a]);
}
}
dfs(1);
for(int i=1;i<=q;i++)
{
if(is_query[i])
cout<<ans[i]<<"\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
96 ms |
24484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
