#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int N = 2e5 + 1;
int n;
struct Query {
int a, t;
Query(int a = 0, int t = 0) : a(a), t(t) {}
};
vector<Query> Q[N];
unsigned char maxBit = 30;
struct trie {
int it;
vector<array<bool, 2>> nwt;
vector<int> t;
void add(int val, int time) {
int g = 0;
for (int j = maxBit; j >= 1; --j) {
int bit = (val >> j - 1 & 1);
while (nwt.size() <= g) nwt.push_back(array<bool, 2>());
if (!nwt[g][bit]) nwt[g][bit] = ++it;
g = nwt[g][bit];
while (t.size() <= it) t.push_back(N);
t[g] = min(t[g], time);
}
}
int get(int val, int time) {
int g = 0;
int ret = 0;
for (int j = maxBit; j >= 1; --j) {
int bit = (val >> j - 1 & 1);
if (nwt[g][!bit] && t[nwt[g][!bit]] <= time) {
ret |= (1 << j - 1);
g = nwt[g][!bit];
} else g = nwt[g][bit];
}
return ret;
}
void clear() {
nwt.clear();
t.clear();
}
} node[N];
vector<pii> ad[N];
int d[N], t[N];
int answer[N];
int it;
int st[N], ed[N], mask[N];
void dfs(int u, int pre = 0) {
mask[st[u] = ++it] = u;
int best = 0;
for (const auto& duck : ad[u]) {
int v, w; tie(v, w) = duck;
if (v == pre) continue;
dfs(v, u);
if (!best || node[v].nwt.size() > node[best].nwt.size()) best = v;
}
swap(node[u], node[best]);
for (const auto& duck : ad[u]) {
int v, w; tie(v, w) = duck;
if (v == pre || v == best) continue;
for (int i = st[v]; i <= ed[v]; ++i) node[u].add(d[mask[i]], t[mask[i]]);
node[v].clear();
}
node[u].add(d[u], t[u]);
for (const auto& duck : Q[u]) {
int a = duck.a, time = duck.t;
answer[time] = node[u].get(d[a], time);
}
ed[u] = it;
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
int cnt = 1;
for (int i = 1; i <= n; ++i) {
string ty;
int x, y;
cin >> ty >> x >> y;
if (ty == "Add") {
cnt += 1;
ad[x].push_back({cnt, y});
ad[cnt].push_back({x, y});
d[cnt] = (d[x] ^ y);
t[cnt] = i;
} else {
Q[y].push_back(Query(x, i));
}
}
memset(answer, -1, sizeof answer);
dfs(1);
for (int i = 1; i <= n; ++i)
if (answer[i] != -1) cout << answer[i] << "\n";
}
Compilation message
klasika.cpp: In member function 'void trie::add(int, int)':
klasika.cpp:26:27: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
26 | int bit = (val >> j - 1 & 1);
| ~~^~~
klasika.cpp:28:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<bool, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
28 | while (nwt.size() <= g) nwt.push_back(array<bool, 2>());
| ~~~~~~~~~~~^~~~
klasika.cpp:33:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
33 | while (t.size() <= it) t.push_back(N);
| ~~~~~~~~~^~~~~
klasika.cpp: In member function 'int trie::get(int, int)':
klasika.cpp:41:27: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
41 | int bit = (val >> j - 1 & 1);
| ~~^~~
klasika.cpp:44:24: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
44 | ret |= (1 << j - 1);
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
23900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
23900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
71 ms |
40760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
23900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
