#include <bits/stdc++.h>
using namespace std;
struct node{
int s,e;
set<int> v;
node *l,*r;
node(int _s, int _e){
s = _s;
e = _e;
if (s!=e){
l = new node(s,(s+e)/2);
r = new node((s+e)/2+1,e);
}
}
void addVal(int pos, int val){
v.insert(val);
if (s==e) return;
if (pos>(s+e)/2){
r->addVal(pos,val);
}
else{
l->addVal(pos,val);
}
}
int query(int a, int b, int val){
if (a<=s && e<=b){
if (v.empty()) return 0;
int lb = 0;
for (int x = 29; x>=0; x--){
int bitmask = ((1<<30)-1-((1<<(x+1))-1));
int pref = (lb&bitmask);
if ((val&(1<<x))==0){
auto it = v.lower_bound(pref+(1<<x));
if (it==v.end()){
continue;
}
int res = *(it);
if ((res&(1<<x))!=0 && (pref==(res&bitmask))){
lb += (1<<x);
}
}
else{
auto it = v.lower_bound(pref);
int res = *(it);
if ((res&(1<<x))!=0){
lb += (1<<x);
}
}
}
/*
printf("node %d to %d: ",s,e);
for (auto x : v){
printf("%d ",x);
}
printf("\n");
printf("chose %d for val %d\n",lb,val);
*/
return lb^val;
}
else if (b<=(s+e)/2){
return l->query(a,b,val);
}
else if (a>(s+e)/2){
return r->query(a,b,val);
}
else{
return max(l->query(a,b,val),r->query(a,b,val));
}
}
}*root;
int order[200005];
int subtree[200005];///subtree size
int dist[200005];///length of path to root
vector<pair<bool,pair<int,int> > > queries; ///offline lol
vector<pair<int,int> > adjl[200005];
int q;
int n = 1;
int cur = 1;
int dfs(int node){
order[node] = cur;
cur++;
subtree[node] = 1;
for (auto x : adjl[node]){
dist[x.first] = dist[node]^x.second;
subtree[node] += dfs(x.first);
}
return subtree[node];
}
int main(){
cin>>q;
for (int x = 0; x<q; x++){
string str;
cin>>str;
int a,b;
cin>>a;
cin>>b;
if (str=="Add"){
n++;
queries.push_back({true,{n,b}});
adjl[a].push_back({n,b});
}
else{
queries.push_back({false,{a,b}});
}
}
root = new node(1,n);
dfs(1);/*
for (int x = 1; x<=n; x++){
printf("%d ",dist[x]);
}
printf("\n");*/
for (auto x : queries){
if (x.first){
//printf("adding %d %d\n",order[x.second.first],dist[x.second.first]);
root->addVal(order[x.second.first],dist[x.second.first]);
}
else{
int xr = dist[x.second.first];
printf("%d\n",root->query(order[x.second.second],order[x.second.second]+subtree[x.second.second]-1,xr));
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5120 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
5120 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5120 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
5120 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
980 ms |
48948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5120 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
5120 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
