| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1293870 | i_love_kim_ji_won | Klasika (COCI20_klasika) | C++20 | 0 ms | 0 KiB |
// I ♡ 김지원
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define freopen(name) if(fopen(name".INP","r")) {freopen (name".INP","r",stdin); freopen (name".OUT","w",stdout);}
using namespace std;
using ll = long long;
void justDoIt();
int main() {
// freopen("");
ios_base::sync_with_stdio(false);
cin.tie(0);
justDoIt();
return 0;
}
const int N = 2e5 + 5;
const int numnodes = 7e6 + 5;
int st[N], en[N];
vector<int> g[N];
string type[N];
int tin[N], tout[N];
int val[N];
// struct Trie {
// struct Node {
// int child[2];
// set<int> s;
// } nodes[numnodes];
// int cur;
// Trie() : cur(0) {
// memset(nodes[0].child, -1, sizeof(nodes[0].child));
// nodes[0].s.clear();
// };
// int new_node() {
// cur++;
// memset(nodes[cur].child, -1, sizeof(nodes[cur].child));
// nodes[cur].s.clear();
// return cur;
// }
// void add_num(int x, int t) {
// int pos = 0;
// for (int i = 30; i >= 0; i--) {
// int c = (x >> i & 1);
// if (nodes[pos].child[c] == -1) {
// nodes[pos].child[c] = new_node();
// }
// pos = nodes[pos].child[c];
// nodes[pos].s.insert(t);
// }
// }
// int query(int x, int l, int r) {
// int res = 0, pos = 0;
// for (int i = 30; i >= 0; i--) {
// for (int v = 1; v >= 0; v--) {
// int c = (v ^ (x >> i & 1));
// if (nodes[pos].child[c] == -1) {continue;}
// auto idx = nodes[nodes[pos].child[c]].s.lower_bound(l);
// if (idx == nodes[nodes[pos].child[c]].s.end() || *idx > r) {continue;}
// pos = nodes[pos].child[c];
// res += (v << i);
// break;
// }
// }
// return res;
// }
// } T;
struct Trie {
struct Node {
Node* child[2];
set<int> s;
Node () {
child[0] = child[1] = NULL;
}
};
int cur;
Node* root;
Trie () : cur(0) {
root = new Node();
};
void add_num(int x, int t) {
Node* p = root;
for (int i = 30; i >= 0; i--) {
int c = (x >> i & 1);
if (p->child[c] == NULL) {
p->child[c] = new Node();
}
p = p-> child[c];
p->s.insert(t);
}
}
int query(int x, int l, int r) {
int res = 0;
Node* p = root;
for (int i = 30; i >= 0; i--) {
int c = (x >> i & 1);
c ^= 1;
if (p->child[c] == NULL ||
p->child[c]->s.lower_bound(l) == p->child[c]->s.upper_bound(r)) {
p = p->child[c ^ 1];
}
else {
res += (1 << i);
p = p->child[c];
}
}
return res;
}
} T;
int timer = 0;
void dfs(int u, int p = 0) {
tin[u] = ++timer;
for (int v : g[u]) {
if (v == p) {continue;}
dfs(v, u);
}
tout[u] = timer;
}
void test() {
int q;
cin >> q;
int curr = 1;
for (int i = 1; i <= q; i++) {
cin >> type[i] >> st[i] >> en[i];
if (type[i] == "Add") {
g[++curr].push_back(st[i]);
g[st[i]].push_back(curr);
val[curr] = val[st[i]] ^ en[i];
}
}
dfs(1);
curr = 1;
T.add_num(val[1], tin[1]);
for (int i = 1; i <= q; i++) {
if (type[i] == "Add") {
curr++;
T.add_num(val[curr], tin[curr]);
}
else {
cout << T.query(val[st[i]], tin[en[i]], tout[en[i]]) << '\n';
}
}
}
void justDoIt() {
int t = 1;
// cin >> t;
for (int tests = 1; tests <= t; tests++) {
test();
}
}