#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 2e5 + 5;
//#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#define OPEN freopen(".in", "r", stdin); \
freopen(".out", "w", stdout);
#else
#define OPEN void(23);
#endif
vector <pair <int, int>> adj[MAXN];
vector <pair <int, int>> radj[MAXN];
int cnt = 2;
int FindAns(int a, int b)
{
vector <bool> sub(cnt + 5);
function <void(int)> dfsSub = [&](int node) -> void
{
//cerr << node << " ";
sub[node] = true;
for(auto &[child, w] : adj[node])
dfsSub(child);
return;
};
dfsSub(b);
int ans = 0;
function <void(int, int, int)> dfs = [&](int node, int par, int sum) -> void
{
if(sub[node]) ans = max(ans, sum);
for(auto &[child, w] : adj[node])
if(child != par)
dfs(child, node, sum ^ w);
for(auto &[child, w] : radj[node])
if(child != par)
dfs(child, node, sum ^ w);
};
dfs(a, 0, 0);
return ans;
}
void solve1(int q, vector <tuple <string, int, int>> &queries)
{
for(int i = 1; i <= q; i++)
{
auto &[str, a, b] = queries[i -1];
if(str[0] == 'A')
{
adj[a].emplace_back(cnt, b);
radj[cnt].emplace_back(a, b);
cnt++;
}
else
{
cout << FindAns(a, b) << "\n";
}
}
return;
}
struct Node
{
int l = -1, r = -1;
Node() {}
};
struct Trie
{
vector <Node> tree;
Trie() {tree.resize(1);}
int cnt = 1;
void add(int x, int node = 0, int bit = 31)
{
if(bit < 0) return;
if(x & 1)
{
if(tree[node].r == -1) tree[node].r = cnt++, tree.emplace_back();
add(x / 2, tree[node].r, bit -1);
}
else
{
if(tree[node].l == -1) tree[node].l = cnt++, tree.emplace_back();
add(x / 2, tree[node].l, bit -1);
}
}
int query(int x, int node = 0, int bit = 31)
{
//cerr << x << " " << node << " " << bit << "\n";
if(bit < 0) return 0;
if(x & 1)
{
if(tree[node].l != -1) return (1 << (31 - bit)) + query(x / 2, tree[node].l, bit -1);
else return query(x / 2, tree[node].r, bit -1);
}
else
{
if(tree[node].r != -1) return (1 << (31 - bit)) + query(x / 2, tree[node].r, bit -1);
else return query(x / 2, tree[node].l, bit -1);
}
}
};
void solve2(int q, vector <tuple <string, int, int>> &queries)
{
Trie trie;
vector <int> dists(2);
trie.add(0);
dists[1] = 0;
for(int i = 1; i <= q; i++)
{
auto &[str, a, b] = queries[i -1];
//cerr << dists[a] << " " << b << "\n";
if(str[0] == 'A')
{
dists.emplace_back(dists[a] ^ b);
trie.add(dists[a] ^ b);
cnt++;
}
else
{
cout << trie.query(dists[a]) << "\n";
}
}
}
int32_t main()
{
OPEN;
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int q; cin >> q;
vector <tuple <string, int, int>> queries(q);
for(auto &[a, b, c] : queries) cin >> a >> b >> c;
bool ok = true;
for(auto &[a, b, c] : queries) ok &= (a[0] == 'Q' ? c == 1 : true);
if(ok) solve2(q, queries);
else solve1(q, queries);
}
Compilation message
klasika.cpp: In function 'int32_t main()':
klasika.cpp:11:25: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
11 | #define OPEN freopen(".in", "r", stdin); \
| ~~~~~~~^~~~~~~~~~~~~~~~~~~
klasika.cpp:141:5: note: in expansion of macro 'OPEN'
141 | OPEN;
| ^~~~
klasika.cpp:12:25: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | freopen(".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
klasika.cpp:141:5: note: in expansion of macro 'OPEN'
141 | OPEN;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
19544 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
19544 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
19804 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
19544 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
