This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
typedef long long lo;
typedef pair< lo,lo > PII;
#define fi first
#define se second
#define mp make_pair
#define int long long
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
const lo inf = 1000000000000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 200002;
const lo mod = 1000000007;
int n,m,b[li],a[li],k,flag,t,say=1,nodee=1,visit[li*30][5],xorr[li],l[li],r[li],x[li],y[li],q;
int cev;
char s[li][10];
//~ set<int> st[li];
vector<int> v,vec[li],vect;
vector<set<int>> st;
inline void build_trie(int xxx){
int node=1;
//~ cout<<xxx<<"*(*(*(\n";
for(int i=0;i<(int)v.size();i++){
st[node].insert(xxx);
if(visit[node][v[i]])node=visit[node][v[i]];
else{
visit[node][v[i]]=++nodee;
node=nodee;
}
}
st[node].insert(xxx);
}
inline void ask_trie(int xx){
int node=1;
//~ cout<<l[xx]<<" : : : "<<r[xx]<<endl;
for(int i=0;i<(int)v.size();i++){
auto it=st[visit[node][!v[i]]].lower_bound(l[xx]);
//~ if(xx==3 && node==1)cout<<node<<"****"<<endl;
//~ if(visit[node][!v[i]]){
int yess=0;
//~ cout<<*it<<endl;
if(it!=st[visit[node][!v[i]]].end()){
//~ if(xx==3)cout<<*it<<endl;
if(visit[node][!v[i]] && *it<=r[xx]){node=visit[node][!v[i]];vect.pb(1);yess=1;}
}
//~ }
if(yess==0){node=visit[node][v[i]];vect.pb(0);}
}
}
inline void dfs(int node,int ata){
l[node]=++q;
r[node]=q;
for(int i=0;i<(int)vec[node].size();i++){
int go=vec[node][i];
if(go==ata)continue;
dfs(go,node);
r[node]=max(r[node],r[go]);
}
}
main(void){
//~ freopen("at.txt","r",stdin);
//~ freopen("att.txt","w",stdout);
scanf("%lld",&t);
//~ set.resize();
for(int i=1;i<=t;i++){
//~ int x,y;
scanf("%s %lld %lld",s[i],&x[i],&y[i]);
if(s[i][0]=='A'){
//~ xorr[++say]=(xorr[x[i]]^y[i]);
vec[x[i]].pb(++say);
vec[say].pb(x[i]);
//~ v.clear();
//~ while(at){
//~ v.pb(at%2);
//~ at/=2;
//~ }
//~ while((int)v.size()<35)v.pb(0);
//~ reverse(v.begin(),v.end());
//~ build_trie();
//~ continue;
}
//~ int at=xorr[x];
//~ v.clear();
//~ while(at){
//~ v.pb(at%2);
//~ at/=2;
//~ }
//~ while((int)v.size()<35)v.pb(0);
//~ reverse(v.begin(),v.end());
//~ vect.clear();
//~ ask_trie();
//~ reverse(vect.begin(),vect.end());
//~ int ans=0;
//~ for(int i=0;i<(int)vect.size();i++){
//~ if(vect[i]==1)ans=(ans^(1ll<<i));
//~ }
//~ printf("%lld\n",ans);
}
dfs(1,0);
st.resize(say*30);
for(int i=1;i<=30;i++)v.pb(0);
build_trie(1);
//~ cout<<l[5]<<" : : "<<r[5]<<" : : "<<xorr[]endl;
say=1;
for(int i=1;i<=t;i++){
if(s[i][0]=='A'){
xorr[++say]=(xorr[x[i]]^y[i]);
//~ vec[x[i]].pb(say);
int at=xorr[say];
//~ vec[say].pb(x[i]);
v.clear();
while(at){
v.pb(at%2);
at/=2;
}
while((int)v.size()<30)v.pb(0);
reverse(v.begin(),v.end());
build_trie(l[say]);
continue;
}
int at=xorr[x[i]];
v.clear();
while(at){
v.pb(at%2);
at/=2;
}
while((int)v.size()<30)v.pb(0);
reverse(v.begin(),v.end());
vect.clear();
ask_trie(y[i]);
reverse(vect.begin(),vect.end());
int ans=0;
for(int j=0;j<(int)vect.size();j++){
if(vect[j]==1)ans=(ans^(1ll<<j));
}
printf("%lld\n",ans);
}
//~ cout<<xorr[3]<<endl;
return 0;
}
Compilation message (stderr)
klasika.cpp:79:10: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(void){
^
klasika.cpp: In function 'int main()':
klasika.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&t);
~~~~~^~~~~~~~~~~
klasika.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s %lld %lld",s[i],&x[i],&y[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |