#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;
const int S = 2500;
struct FT{
vector<int> bit;
int n;
void init(int ns){
n = ns;
bit.resize(n + 1);
}
void add(int v, int x){
while (v <= n){
bit[v] += x;
v |= (v + 1);
}
}
int get(int v){
int out = 0;
while (v > 0){
out += bit[v];
v = (v & (v + 1)) - 1;
}
return out;
}
int get(int l, int r){
return get(r) - get(l - 1);
}
};
struct TR{
struct node{
vector<int> all;
int nt[2];
node(){
nt[0] = nt[1] = 0;
}
};
vector<node> t;
vector<int> g;
FT T[100];
int cc, n, cc1 = 0;
void init(int ns, int q){
t.pb({});
t.pb({});
cc = 1;
cc1 = 0;
n = ns;
g.resize(q * lg + 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({});
}
v = t[v].nt[bit];
t[v].all.pb(p);
if (t[v].all.size() >= S){
if (!g[v]){
g[v] = ++cc1;
T[cc1].init(n);
for (int i: t[v].all){
T[cc1].add(i, 1);
}
continue;
}
T[g[v]].add(p, 1);
}
}
}
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 (k > 0){
bool ind = 0;
if (t[k].all.size() < S){
for (int i: t[k].all){
if (l <= i && i <= r){
ind = 1;
break;
}
}
}
else {
ind = (T[g[v]].get(l, r) > 0);
}
if (ind){
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];
bool ind = 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 {
if (y != 1) ind = 0;
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, q);
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";
}
}
}
Compilation message
klasika.cpp: In function 'int main()':
klasika.cpp:120:10: warning: variable 'ind' set but not used [-Wunused-but-set-variable]
120 | bool ind = 1;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
201 ms |
94736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
