#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define REP(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
#define mp make_pair
#define all(v) v.begin(), v.end()
#define uni(v) v.erase(unique(all(v)), v.end())
#define Bit(x, i) ((x >> (i)) & 1)
#define Mask(i) (1 << (i))
#define Cnt(x) __builtin_popcount(x)
#define Cntll(x) __builtin_popcountll(x)
#define Ctz(x) __builtin_ctz(x) // so luong so 0 tinh tu ben phai
#define Ctzll(x) __builtin_ctzll(x)
#define Clz(x) __builtin_clz(x) // so luong so 0 tinh tu ben trai
#define Clzll(x) __builtin_clzll(x)
inline bool maximize(int &u, int v){
return v > u ? u = v, true : false;
}
inline bool minimize(int &u, int v){
return v < u ? u = v, true : false;
}
inline bool maximizell(long long &u, long long v){
return v > u ? u = v, true : false;
}
inline bool minimizell(long long &u, long long v){
return v < u ? u = v, true : false;
}
const int mod = 1e9 + 7;
inline int fastPow(int a, int n){
if(n == 0) return 1;
int t = fastPow(a, n >> 1);
t = 1ll * t * t % mod;
if(n & 1) t = 1ll * t * a % mod;
return t;
}
//inline void add(int &u, int v){
// u += v;
// if(u >= mod) u -= mod;
//}
//inline void sub(int &u, int v){
// u -= v;
// if(u < 0) u += mod;
//}
const int maxN = 2e5 + 5;
const int inf = 1e9;
const long long infll = 1e18;
int q, n;
int type[maxN];
int X[maxN], Y[maxN];
vector<pair<int, int>> child[maxN];
vector<pair<int, int>> query[maxN];
int hv[maxN], sz[maxN], sum[maxN], d[maxN];
int in[maxN], out[maxN], id[maxN], timeDfs;
void dfs(int u = 1){
sz[u] = 1;
in[u] = ++timeDfs;
id[timeDfs] = u;
for(auto[v, w] : child[u]){
sum[v] = sum[u] ^ w;
d[v] = d[u] + 1;
dfs(v);
sz[u] += sz[v];
if(sz[v] > sz[hv[u]])hv[u] = v;
}
out[u] = timeDfs;
}
struct Trie{
Trie *child[2];
set<int> node;
Trie(){
FOR(i, 0, 1)child[i] = nullptr;
}
}*root;
void add(int u, int val){
Trie *p = root;
bitset<30> b(val);
for(int i = 30; i >= 0; --i){
int cur = Bit(val, i);
if(p -> child[cur] == nullptr) p -> child[cur] = new Trie();
p = p -> child[cur];
p -> node.insert(u);
}
}
void del(int u, int val){
Trie *p = root;
for(int i = 30; i >= 0; --i){
int cur = Bit(val, i);
Trie *pre = p;
p = p -> child[cur];
p -> node.erase(u);
if(p -> node.empty()) pre -> child[cur] = nullptr;
}
}
int get(int val, int maxNode){
Trie *p = root;
int answer = 0;
for(int i = 30; i >= 0; --i){
int cur = Bit(val, i);
if(p -> child[cur ^ 1] != nullptr){
if(* p -> child[cur ^ 1] -> node.begin() <= maxNode){
answer |= Mask(i);
p = p -> child[cur ^ 1];
}else{
p = p -> child[cur];
}
}else{
p = p -> child[cur];
}
}
return answer;
}
int res[maxN];
void sack(int u = 1){
for(auto[v, w] : child[u]){
if(v != hv[u]){
sack(v);
FOR(i, in[v], out[v]) del(id[i], sum[id[i]]);
}
}
if(hv[u]) sack(hv[u]);
add(u, sum[u]);
for(auto[v, w] : child[u]){
if(v != hv[u]){
FOR(i, in[v], out[v]) add(id[i], sum[id[i]]);
}
}
for(auto[id, maxNode] : query[u]){
int a = X[id];
res[id] = get(sum[a], maxNode);
}
}
void process(){
cin >> q;
n = 1;
root = new Trie();
FOR(i, 1, q){
string s;
cin >> s >> X[i] >> Y[i];
if(s[0] == 'A')type[i] = 1;
else type[i] = 2;
if(type[i] == 1){
++n;
child[X[i]].emplace_back(n, Y[i]);
}
else{
query[Y[i]].emplace_back(i, n);
}
}
dfs();
sack();
FOR(i, 1, q){
if(type[i] == 2){
cout << res[i] << '\n';
}
}
}
#define LOVE ""
int main(){
if(fopen(LOVE".inp", "r")){
freopen(LOVE".inp", "r", stdin);
freopen(LOVE".out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while(t--)
process();
// cerr << '\n' << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s\n" ;
return 0;
}
Compilation message (stderr)
klasika.cpp: In function 'int main()':
klasika.cpp:163:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
163 | freopen(LOVE".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:164:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
164 | freopen(LOVE".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |