#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _3qplfh5 ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
using tupiii=tuple<int,int,int>;
using pii=pair<int,int>;
using vi=vector<int>;
using vll=vector<long long>;
int main(){
_3qplfh5;
int q;
cin>>q;
vec(tupiii) qry;
int n=1;
rep(_,q){
string s;
cin>>s;
int t=0;
if(s=="Add"){
t=1;
n++;
}
int _a,_b;
cin>>_a>>_b;
qry.pb({t,_a,_b});
}
vec(vec(pii)) adj(n);
int now=1;
for(auto [t,_a,_b] : qry){
if(t==1){
adj[_a-1].pb({now,_b});
adj[now].pb({_a-1,_b});
now++;
}
}
//rabbit tour
vi tour;
vi tin(n,0),tout(n,0);
vi psum(n,0);
int tm=0;
auto dfs=[&](auto self,int v,int par)->void{
tin[v]=tm++;
tour.pb(v);
for(auto edge : adj[v]){
int u=edge.fi;
if(u!=par){
psum[u]=psum[v]^edge.se;
// cout<<edge.se<<"\n";
self(self,u,v);
}
}
tout[v]=tm++;
tour.pb(v);
};
dfs(dfs,0,-1);
vec(std::map<ll,set<int>>) rbts(32);
now=1;
for(auto [t,_a,_b] : qry){
if(t==0){
_a--,_b--;
int k=psum[_a];
int need=0;
drep(j,31){
if(!(k&(1<<j))){
need|=(1<<j);
}
bool pokita=0;
if(rbts[j].find(need)!=rbts[j].end()){
auto it=rbts[j][need].lower_bound(tin[_b]);
if(it!=rbts[j][need].end() and *it<tout[_b]){
pokita=1;
}else{
auto ti=rbts[j][need^(1<<j)].lower_bound(tin[_b]);
assert(ti!=rbts[j][need^(1<<j)].end() and *ti<tout[_b]);
}
}
if(not pokita){
need^=(1<<j);
}
}
// cout<<need<<"\n";
cout<<(need^k)<<"\n";
}else{
int v=now;
int wata=0;
drep(j,31){
if(psum[v]&(1<<j)) wata|=(1<<j);
rbts[j][wata].insert(tin[v]);
}
// cout<<v<<" "<<psum[v]<<" "<<wata<<"\n";
now++;
}
}
//
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
588 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
588 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2309 ms |
126976 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
588 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
