#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define arr3 array<int, 3>
const int lg = 31;
struct ST{
struct node{
node *l, *r;
node(){
l = r = 0;
}
node(node *ls, node *rs){
l = ls; r = rs;
}
};
node *rt;
int n;
void init(int ns){
n = ns;
rt = new node();
}
node* add(node *v, int tl, int tr, int& x){
if (tl == tr) return new node();
int tm = (tl + tr) / 2;
if (x <= tm){
if (!(v -> l)) v -> l = new node();
return new node(add(v -> l, tl, tm, x), v -> r);
}
if (!(v -> r)) v -> r = new node();
return new node(v -> l, add(v -> r, tm + 1, tr, x));
}
void add(int x){
rt = add(rt, 1, n, x);
}
bool get(node *v, int tl, int tr, int& l, int& r){
if (l > tr || r < tl) return 0;
if (l <= tl && tr <= r) return 1;
int tm = (tl + tr) / 2;
if (v -> l && get(v -> l, tl, tm, l, r)) return 1;
if (v -> r && get(v -> r, tm + 1, tr, l, r)) return 1;
return 0;
}
bool get(int l, int r){
return get(rt, 1, n, l, r);
}
};
struct TR{
struct node{
ST T;
int nt[2];
node(int n){
nt[0] = nt[1] = 0;
T.init(n);
}
};
vector<node> t;
int cc, n;
void init(int ns){
n = ns;
t.pb(node(n));
t.pb(node(n));
cc = 1;
}
vector<int> :: iterator it;
void add(int x, int p){
int v = 1;
for (int i = lg; i >= 0; i--){
bool bit = (x >> i) & 1;
if (!t[v].nt[bit]){
t[v].nt[bit] = ++cc;
t.pb(node(n));
}
v = t[v].nt[bit];
t[v].T.add(p);
}
}
int get(int l, int r, int x){
int out = 0, v = 1;
for (int i = lg; i >= 0; i--){
bool bit = (x >> i) & 1;
int k = t[v].nt[!bit];
if (t[k].T.get(l, r)){
v = k;
out += (1 << i);
continue;
}
v = t[v].nt[bit];
}
return out;
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int q, cc = 1; cin>>q;
vector<arr3> qs;
vector<pii> g[q + 1];
for (int i = 1; i <= q; i++){
string type; int x, y; cin>>type>>x>>y;
if (type[0] == 'A'){
cc++;
g[x].pb({cc, y});
qs.pb({0, x, cc});
}
else {
qs.pb({1, x, y});
}
}
int n = cc;
vector<int> tin(n + 1), tout(n + 1), d(n + 1);
int timer = 0;
function<void(int)> fill = [&](int v){
tin[v] = ++timer;
for (auto [i, w]: g[v]){
d[i] = d[v] ^ w;
fill(i);
}
tout[v] = timer;
};
fill(1);
TR T; T.init(n);
T.add(0, 1);
for (auto [type, x, y]: qs){
if (!type){
T.add(d[y], tin[y]);
}
else {
cout<<T.get(tin[y], tout[y], d[x])<<"\n";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
519 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
