#include<bits/stdc++.h>
using namespace std;
int n = 1;
vector <vector <pair <int, int> > > g;
vector <int> h, tin, tout;
int timer = 0;
void dfs(int v, int p = -1)
{
tin[v] = timer++;
for(int i = 0; i < g[v].size(); i++)
{
int to = g[v][i].first;
int w = g[v][i].second;
if(to != p)
{
h[to] = h[v] ^ w;
dfs(to, v);
}
}
tout[v] = timer - 1;
}
struct node{
node* left;
node* right;
node(){
left = NULL;
right = NULL;};
};
vector <node*> tree;
void go_down(node* &w, int i, int val)
{
if(i < 0)
{
return;
}
if(val & (1 << i))
{
if(!w -> right)
{
w -> right = new node();
}
go_down(w -> right, i - 1, val);
}
else
{
if(!w -> left)
{
w -> left = new node();
}
go_down(w -> left, i - 1, val);
}
}
void update(int v, int l, int r, int ind, int val)
{
go_down(tree[v], 29, val);
if(l == r)
{
return;
}
if(ind <= (r + l) / 2)
{
update(v * 2, l, (r + l) / 2, ind, val);
}
else
{
update(v * 2 + 1, (r + l) / 2 + 1, r, ind, val);
}
}
int ans(int v, int l, int r, int al, int ar, int val)
{
if(l >= al && r <= ar)
{
if(!tree[v] -> left && !tree[v] -> right)
{
return val;
}
int val1 = (1 << 30) - val - 1;
node* w = tree[v];
int valans = 0;
for(int i = 29; i >= 0; i--)
{
if(val1 & (1 << i))
{
if(!w -> right)
{
w = w -> left;
}
else
{
w = w -> right;
valans += (1 << i);
}
}
else
{
if(!w -> left)
{
w = w -> right;
valans += (1 << i);
}
else
{
w = w -> left;
}
}
}
return valans;
}
else if(l <= ar && r >= al)
{
int t1 = ans(v * 2, l, (r + l) / 2, al, ar, val);
int t2 = ans(v * 2 + 1, (r + l) / 2 + 1, r, al, ar, val);
if((t1 ^ val) > (t2 ^ val))
{
return t1;
}
return t2;
}
else
{
return val;
}
}
signed main(){
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
// cout.tie(NULL);
int q;
cin >> q;
vector <string> type(q);
vector <pair <int, int> > mass(q);
for(int i = 0; i < q; i++){
cin >> type[i];
cin >> mass[i].first >> mass[i].second;
if(type[i] == "Add"){
n++;
}
}
g.resize(n);
h.resize(n);
tin.resize(n);
tout.resize(n);
int cnt = 1;
for(int i = 0; i < q; i++)
{
if(type[i] == "Add")
{
mass[i].first--;
g[mass[i].first].push_back({cnt, mass[i].second});
cnt++;
}
}
dfs(0);
tree.resize(4 * n);
for(int i = 0; i < 4 * n; i++){
tree[i] = new node();
}
cnt = 1;
for(int i = 0; i < q; i++)
{
if(type[i] == "Add")
{
update(1, 0, n - 1, tin[cnt], h[cnt]);
cnt++;
}
else
{
mass[i].first--;
mass[i].second--;
int val = h[mass[i].first];
int val1 = ans(1, 0, n - 1, tin[mass[i].second], tout[mass[i].second], val);
cout << (val ^ val1) << "\n";
}
}
return 0;
}
Compilation message
klasika.cpp: In function 'void dfs(int, int)':
klasika.cpp:11:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[v].size(); i++)
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
640 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
768 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
640 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
768 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1161 ms |
499984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
640 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
768 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
