#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define pii array<int,2>
#define tii array<int,3>
struct Node {
pii cld = {-1, -1};
set<int> tm;
};
Node root;
vector<Node> trie = {root};
void insert(int val, int ndtm) {
int idx = 0;
trie[idx].tm.insert(ndtm);
for (int i=30;i>=0;i--) {
int b1 = 0;
if (((1<<i)&val) != 0) b1 = 1;
if (trie[idx].cld[b1] == -1) {
Node n1;
trie.push_back(n1);
trie[idx].cld[b1] = (int)trie.size()-1;
}
idx = trie[idx].cld[b1];
trie[idx].tm.insert(ndtm);
}
}
const int FLL = (((int)1)<<35)-1;
int gret(int val, int start, int end) {
int idx = 0;
for (int i=30;i>=0;i--) {
int b1 = 0;
if (((1<<i)&val) != 0) b1 = 1;
int b2 = 1 - b1;
if (trie[idx].cld[b2] != -1) {
auto it = trie[trie[idx].cld[b2]].tm.lower_bound(start);
if (it != trie[trie[idx].cld[b2]].tm.end() && (*it) < end) {
val = (val | (1<<i));
idx = trie[idx].cld[b2];
continue;
}
}
idx = trie[idx].cld[b1];
val = (val & (FLL ^ (1<<i)));
}
return val;
}
signed main() {
int q;cin>>q;
vector<tii> quer;
vector<vector<int>> child(1);
vector<int> val = {0};
while (q--) {
string s;cin>>s;
if (s == "Add") {
int x,y;cin>>x>>y;x--;
child.push_back({});
child[x].push_back((int)child.size()-1);
val.push_back(y);
quer.push_back({0, x, y});
}
else {
int a,b;cin>>a>>b;
a--;b--;
quer.push_back({1, a, b});
}
}
int n = (int)child.size();
vector<int> tin(n, -1), tout(n, -1);
int cnt = 0;
vector<int> pfsm(n, 0);
function<void(int)> dfs=[&](int node) {
tin[node] = cnt++;
for (auto &x:child[node]) {
pfsm[x] = (pfsm[node] ^ val[x]);
dfs(x);
}
tout[node] = cnt;
};
dfs(0);
cnt = 1;
for (auto &x:quer) {
if (x[0] == 0) {
insert(pfsm[cnt], tin[cnt]);
cnt++;
}
else {
auto [t, a, b] = x;
int v1 = pfsm[a];
int res = gret(v1, tin[b], tout[b]);
cout << res << endl;
}
}
}
# | 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... |