/*
++[---------->+<]>.-[------>+<]>-.++++++++.+++++.-[->+++++<]>-.-[--->++<]>--.+.[--->+<]>---.[->+++<]>++.++++++.-------.++++++.--[--->+<]>.-[->+++<]>-..+++++++++++++.[----->++<]>.------------.+[----->+<]>.--------.+++++++++++++.-------------.--[--->+<]>-.---[->++++<]>-.++++[->+++<]>.--[--->+<]>-.[->+++<]>++.-.+++.---.-[->+++<]>.-[--->++<]>+.++++.------.[--->+<]>---.+[----->+<]>.------------.+++++++.-------.--[--->+<]>---.+++[->+++<]>++..+++++++++.---------.-[->+++<]>.+[----->+<]>+.-------------.+++++++.+.----[->+++<]>-.
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long big;
typedef long double ludo;
#define pbb pair<big, big>
#define pii pair<int, int>
#define fe first
#define se second
#define maxheap priority_queue
#define mset multiset
#define uset unordered_set
#define umap unordered_map
#define fr(i, s, e) for(int i = s; i < e; i++)
#define revfr(i, s, e) for(int i = s - 1; i >= e; i--)
#define getv(v, n) for(int i = 0; i < n; i++) cin >> v[i];
#define speed ios_base::sync_with_stdio(false); cin.tie(NULL)
#define nl "\n"
// #define debug(text) if(do_debug) {cout << (#text) << ": " << text << endl;}
#ifdef naman1601
#define debug(text) cout << (#text) << ": " << text << endl;
#else
#define debug(text)
#endif
const big mod = 1000000007;
// const big mod = 998244353;
const big infinity = 1000000000000000000;
const int inf = 1e9 + 5;
bool do_debug = false;
const int maxn = 2e5 + 5;
int n_nodes;
int size_of_tree;
vector<pii> adj[maxn];
vector<array<big, 3>> queries;
int mapper[maxn] = {0}, in[maxn] = {0}, out[maxn] = {0}, from_root[maxn] = {0};
struct node {
int leaf = 0;
int next[2] = {0};
set<int> set_in;
};
vector<node> trie(1);
void add(big val, int node) {
int v = 0;
revfr(bit, 31, 0) {
int is_set = 0;
if(val & (1 << bit)) {
is_set++;
}
if(!trie[v].next[is_set]) {
trie[v].next[is_set] = trie.size();
trie.emplace_back();
}
v = trie[v].next[is_set];
trie[v].set_in.insert(in[node]);
}
trie[v].leaf = 1;
}
big query(big val, int node) {
int v = 0;
big rv = 0;
revfr(bit, 31, 0) {
int is_set = 0;
if(val & (1 << bit)) {
is_set++;
}
int preferred = !is_set;
int not_preferred = !preferred;
if(trie[v].next[preferred]) {
auto it = trie[trie[v].next[preferred]].set_in.lower_bound(in[node]);
if(it != trie[trie[v].next[preferred]].set_in.end() && *it <= out[node]) {
rv ^= preferred * (1 << bit);
v = trie[v].next[preferred];
} else {
rv ^= not_preferred * (1 << bit);
v = trie[v].next[not_preferred];
}
} else {
rv ^= not_preferred * (1 << bit);
v = trie[v].next[not_preferred];
}
}
return rv;
}
void dfs(int v, int p) {
in[v] = size_of_tree++;
for(auto edge : adj[v]) {
int u = edge.fe;
if(u == p) {
continue;
}
dfs(u, v);
}
out[v] = size_of_tree - 1;
}
void solve() {
int nq;
cin >> nq;
queries.reserve(nq);
size_of_tree = 1;
fr(i, 0, nq) {
string type;
int ty = 2;
big u, v;
cin >> type >> u >> v;
if(type == "Add") {
ty = 1;
size_of_tree++;
adj[u].push_back(make_pair(size_of_tree, v));
}
queries.push_back({ty, u, v});
}
size_of_tree = 0;
dfs(1, 1);
size_of_tree = 1;
// for(auto q : queries) {
// if(q[0] == 2) {
// continue;
// }
// size_of_tree++;
// from_root[size_of_tree] = from_root[q[1]] ^ q[2];
// add(from_root[size_of_tree], size_of_tree);
// }
for(auto q : queries) {
if(q[0] == 1) {
size_of_tree++;
from_root[size_of_tree] = from_root[q[1]] ^ q[2];
add(from_root[size_of_tree], size_of_tree);
continue;
}
int u = q[1], v = q[2];
big ans = from_root[u];
ans ^= query(ans, v);
cout << ans << nl;
}
}
int main() {
speed;
int q = 1;
// cin >> q;
while(q-- > 0) {
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5196 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5196 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5196 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5196 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
932 ms |
127700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5196 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5196 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
