#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define pb push_back
#define ss second
#define ff first
#define all(x) (x).begin(), (x).end()
const int nax = 2e5 + 4;
int q, n = 1, k = 1;
int sp[nax][20], d[nax], dep[nax], eul[nax], eulend[nax];
int cureul = -1;
vector<pii> adj[nax];
struct node
{
int layer = 0;
node *zer, *one;
node(): layer(0), zer(nullptr), one(nullptr){}
node (int d, node *ll, node *rr)
{
zer = ll, one = rr;
layer= d;
}
node(node *cp): layer(cp->layer), zer(cp->zer), one(cp->one) {}
};
node *update(node *Node, int val, int d)
{
if(d == 0)
return new node();
if(val & (1 << (d - 1)))
{
if(Node->one == nullptr)
Node->one = new node(d - 1, nullptr, nullptr);
return new node(d, Node->zer, update(Node->one, val, d - 1));
}
else
{
if(Node->zer == nullptr)
Node->zer = new node(d - 1, nullptr, nullptr);
return new node(d, update(Node->zer, val, d - 1), Node->one);
}
}
node *roots[4 * nax];
int query(node *Node, int val)
{
if(Node->layer == 0)
return 0;
// cout << Node->layer << ' ' << val << '\n';
if(val & (1 << (Node->layer - 1)))
{
if(Node->zer != nullptr)
return (1 << (Node->layer - 1)) + query(Node->zer, val);
else
return query(Node->one, val);
}
else
{
if(Node->one != nullptr)
return (1 << (Node->layer - 1)) + query(Node->one, val);
else
return query(Node->zer, val);
}
}
void pupd(int i, int val)
{
i += k;
if(roots[i] == nullptr)
roots[i] = new node(30, nullptr, nullptr);
roots[i] = update(roots[i], val, 30);
// cout << i << endl;
i /= 2;
while(i)
{
//cout << i << endl;
if(roots[i] == nullptr)
roots[i] = new node(30, nullptr, nullptr);
roots[i] = update(roots[i], val, 30);
i /= 2;
}
}
int squery(int p, int l, int r, int i, int j, int val)
{
if(i > j)
return 0;
if(l >= i && r <= j)
{
if(roots[p] != nullptr)
return query(roots[p], val);
else
return 0;
}
int m = (l + r)/2;
return max(squery(2 * p, l, m, i, min(j, m), val),
squery(2 * p + 1, m + 1, r, max(i, m + 1), j, val));
}
void dfs(int x, int p)
{
eul[x] = ++cureul;
sp[x][0] = p;
for(auto e: adj[x])
{
d[e.ff] = d[x]^e.ss;
dep[e.ff] = dep[x] + 1;
dfs(e.ff, x);
}
eulend[x] = cureul;
}
void bbuild(int p, int l, int r)
{
if(l == r)
{
int curl = 0;
while(curl <= 30)
roots[p] = new node(curl++, roots[p], nullptr);
return ;
}
bbuild(2 * p, l, (l + r)/2);
bbuild(2 * p + 1, (l + r)/2 + 1, r);
roots[p] = new node(roots[2 * p]);
}
int jump(int a, int k)
{
for(int i =0 ;i < 20; i++)
if((1 << i) & k)
a= sp[a][i];
}
int lca(int a, int b)
{
if(dep[a] < dep[b])
swap(a, b);
a = jump(a, dep[a] - dep[b]);
if(a == b)
return a;
}
void solve()
{
cin >> q;
vector<pair<int,pii>> queries;
for(int i = 1; i <= q; i++)
{
string s; cin >> s;
int x, y;
cin >> x >> y;
if(s== "Add")
{
adj[x].pb({++n, y});
x = n;
}
queries.pb({(s == "Query"), {x, y}});
}
dfs(1, 0);
while(k < n)
k = (k << 1);
//bbuild(1, 0, k - 1);
pupd(0, 0);
// cout << squery(1, 0, k - 1, eul[1], eulend[1], d[1]) << '\n';
for(auto e: queries)
{
if(e.ff == 0)
{
//cout << e.ss.ff << ' ' << eul[e.ss.ff] << endl;
update(roots[1], d[e.ss.ff], 30);
}
else
{
int a = e.ss.ff;
int b = e.ss.ss;
// cout << a << ' ' << b << endl;
cout << query(roots[1], d[a]) << '\n';
}
}
}
int32_t main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int tt = 1;
while(tt--)
solve();
}
Compilation message
klasika.cpp: In function 'int jump(int, int)':
klasika.cpp:140:1: warning: no return statement in function returning non-void [-Wreturn-type]
140 | }
| ^
klasika.cpp: In function 'void solve()':
klasika.cpp:184:17: warning: unused variable 'b' [-Wunused-variable]
184 | int b = e.ss.ss;
| ^
klasika.cpp: In function 'int lca(int, int)':
klasika.cpp:149:1: warning: control reaches end of non-void function [-Wreturn-type]
149 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
185 ms |
76572 KB |
Output is correct |
| 2 |
Correct |
271 ms |
139156 KB |
Output is correct |
| 3 |
Correct |
327 ms |
199732 KB |
Output is correct |
| 4 |
Correct |
367 ms |
260696 KB |
Output is correct |
| 5 |
Correct |
193 ms |
75032 KB |
Output is correct |
| 6 |
Correct |
250 ms |
135948 KB |
Output is correct |
| 7 |
Correct |
333 ms |
194876 KB |
Output is correct |
| 8 |
Correct |
403 ms |
254168 KB |
Output is correct |
| 9 |
Correct |
186 ms |
74812 KB |
Output is correct |
| 10 |
Correct |
257 ms |
136692 KB |
Output is correct |
| 11 |
Correct |
306 ms |
196672 KB |
Output is correct |
| 12 |
Correct |
346 ms |
255696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
