/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
struct trie
{
trie *child[2];
int depth;
trie(int _depth)
{
depth = _depth;
child[0] = child[1] = NULL;
}
};
const int maxn = 200100;
struct query
{
int x, y;
string type;
}ask[maxn];
int n = 1, q;
vector < pair < int, int > > g[maxn];
int xor_depth[maxn], f[maxn], timer, tin[maxn], tout[maxn];
void dfs(int v)
{
f[++ timer] = v;
tin[v] = timer;
for (pair < int, int > nb : g[v])
{
int u = nb.first;
xor_depth[u] = (xor_depth[v] ^ nb.second);
dfs(u);
}
tout[v] = timer;
}
trie *tree[4 * maxn];
void build_tree(int root, int left, int right)
{
tree[root] = new trie(29);
if (left == right)
return;
int mid = (left + right) / 2;
build_tree(root * 2, left, mid);
build_tree(root * 2 + 1, mid + 1, right);
}
void add(trie *root, int &num)
{
if (root -> depth < 0)
return;
int bit = ((1 << root -> depth) & num), type = (bit > 0);
if (root -> child[type] == NULL)
root -> child[type] = new trie(root -> depth - 1);
add(root -> child[type], num);
}
int query_xor(trie *root, int x)
{
if (root -> depth < 0)
return 0;
int bit = (1 << root -> depth), type = ((bit & x) > 0);
if (root -> child[(type + 1) % 2] != NULL)
return query_xor(root -> child[(type + 1) % 2], x) + bit;
if (root -> child[type] == NULL)
exit(0);
return query_xor(root -> child[type], x);
}
void update_node(int root, int val)
{
add(tree[root], val);
}
void update(int root, int left, int right, int pos, int val)
{
update_node(root, val);
if (left == right)
return;
int mid = (left + right) / 2;
if (pos <= mid)
update(root * 2, left, mid, pos, val);
else
update(root * 2 + 1, mid + 1, right, pos, val);
}
int query_node(int root, int val)
{
return query_xor(tree[root], val);
}
int query_range(int root, int left, int right, int qleft, int qright, int val)
{
if (left > qright || right < qleft)
return 0;
if (left >= qleft && right <= qright)
return query_node(root, val);
int mid = (left + right) / 2;
return max(query_range(root * 2, left, mid, qleft, qright, val),
query_range(root * 2 + 1, mid + 1, right, qleft, qright, val));
}
void add_node(int ver)
{
update(1, 1, n, tin[ver], xor_depth[ver]);
}
void solve()
{
cin >> q;
for (int i = 1; i <= q; i ++)
{
cin >> ask[i].type >> ask[i].x >> ask[i].y;
if (ask[i].type == "Add")
g[ask[i].x].push_back({++ n, ask[i].y});
}
dfs(1);
build_tree(1, 1, n);
add_node(1);
int ver_cnt = 1;
for (int i = 1; i <= q; i ++)
{
if (ask[i].type == "Add")
{
add_node(++ ver_cnt);
}
else
{
int a = ask[i].x, b = ask[i].y;
int ans = query_range(1, 1, n, tin[b], tout[b], xor_depth[a]);
cout << ans << endl;
}
}
}
int main()
{
speed();
solve();
return 0;
}
/**
2
Add 1 5
Query 1 1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
12884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
12884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
716 ms |
497460 KB |
Output is correct |
| 2 |
Runtime error |
699 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
12884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
