#include <bits/stdc++.h>
using namespace std;
#define needforspeed ios::sync_with_stdio(0);cin.tie(0);
#define int long long int
#define pb push_back
#define ins insert
#define endl '\n'
#define putr(x) cout<<x<<endl;return;
#define all(x) x.begin(),x.end()
#define _ << " " <<
const int mod = 1e9 +7,sze = 8e6 +23,inf = INT_MAX, L = 31;
int T[sze][2];
set<int> fener[sze][2];
int tnod = 1;
int discover[sze];
int finish[sze];
vector<pair<int,int>> graph[sze];
void add(int node,int bit,int val,int gir){
if(bit<0){
return;
}
int x =0;
if(val & (1<<bit)){
x=1;
}
if(T[node][x]==0){
T[node][x]= ( ++tnod);
}
// cout<<bit<<" added "<<val<<" "<<x<<endl;
fener[node][x].ins(gir);
add(T[node][x],bit-1,val,gir);
}
int timer =0;
int pref[sze];
void dfs(int node,int par,int px){
discover[node]=++timer;
pref[node]=px;
for(auto v:graph[node]){
if(v.first!=par){
dfs(v.first,node,px ^ v.second);
}
}
finish[node]=++timer;
}
int qry(int node,int bit,int val,int l,int r){
if(bit<0){
return 0;
}
int lazim =1;
if(val & (1<<bit)){
lazim=0;
}
// cout<<bit<<" "<<val<<" "<<lazim<<" "<<T[node][lazim]<<endl;
if(T[node][lazim] && fener[node][lazim].lower_bound(l) != fener[node][lazim].upper_bound(r)){
return (1<<bit) + qry(T[node][lazim],bit-1,val,l,r);
}
else{
return qry(T[node][1 - lazim],bit-1,val,l,r);
}
}
void opt1z(){
int q;
cin>>q;
int nodec =2;
vector<pair<int, pair<int,int>>> queries;
for(int i=0;i<q;i++){
string op;cin>>op;
int a,b;
cin>>a>>b;
if(op=="Add"){
graph[a].pb({nodec,b});
graph[nodec].pb({a,b});
queries.pb({0,{nodec,b}});
nodec++;
}
else{
queries.pb({1,{a,b}});
}
}
dfs(1,-1,0);
add(1,L,0,discover[1]);
// cout<<pref[2]<<endl;
for(auto v:queries){
auto [a,b] = v.second;
if(v.first ==0){
add(1,L,pref[a],discover[a]);
}
else{
// cout<<"sa"<<endl;
cout<<qry(1,L,pref[a],discover[b],finish[b])<<endl;
}
}
}
signed main() {
needforspeed;
int tt = 1;
// cin>>tt;
while(tt--){
opt1z();
}
return 0;
}
Compilation message
klasika.cpp: In function 'void opt1z()':
klasika.cpp:86:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
86 | auto [a,b] = v.second;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
207 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
207 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
199 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
207 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
