#include <bits/stdc++.h>
#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
#define SZ(x) (int) x.size()
#define F first
#define S second
#define lc id << 1
#define rc lc | 1
const int N = 2e5 + 10;
struct Node {
int ptr; vector<int> trie[2];
void add(int x) {
int v = 0;
for (int i = 30; i >= 0; i--) {
int b = bool(x & (1 << i));
if (!trie[b][v]) trie[b][v] = ptr++;
v = trie[b][v];
}
}
int get(int x) {
if (ptr == 1) return 0;
int v = 0, res = 0;
for (int i = 30; i >= 0; i--) {
int b = bool(x & (1 << i));
if (trie[!b][v]) v = trie[!b][v], res += 1 << i;
else v = trie[b][v];
}
return res;
}
};
int type[N], X[N], Y[N], St[N], Ft[N], n = 1, q, tim, H[N];
vector<pii> adj[N]; Node seg[N << 2];
void DFS(int v, int p = -1) {
St[v] = tim++;
for (pii u : adj[v]) {
if (u.F != p) {
H[u.F] = H[v] ^ u.S;
DFS(u.F, v);
}
}
Ft[v] = tim;
}
void build(int id = 1, int l = 0, int r = tim) {
seg[id].ptr = 1;
seg[id].trie[0].resize((r - l) * 20, 0);
seg[id].trie[1].resize((r - l) * 20, 0);
if (r - l == 1) return;
int mid = (l + r) >> 1;
build(lc, l, mid);
build(rc, mid, r);
}
void add(int pos, int x, int id = 1, int l = 0, int r = tim) {
seg[id].add(x);
if (r - l == 1) return;
int mid = (l + r) >> 1;
if (pos < mid) add(pos, x, lc, l, mid);
else add(pos, x, rc, mid, r);
}
int get(int ql, int qr, int x, int id = 1, int l = 0, int r = tim) {
if (qr <= l || r <= ql) return 0;
if (ql <= l && r <= qr) return seg[id].get(x);
int mid = (l + r) >> 1;
return max(get(ql, qr, x, lc, l, mid), get(ql, qr, x, rc, mid, r));
}
int main() {
scanf("%d", &q);
for (int i = 1; i <= q; i++) {
string t;
cin >> t >> X[i] >> Y[i];
if (t == "Add") {
type[i] = 0;
adj[X[i]].push_back({++n, Y[i]});
} else {
type[i] = 1;
}
}
DFS(1);
build();
add(0, 0);
n = 1;
for (int i = 1; i <= q; i++) {
if (type[i]) {
printf("%lld\n", get(St[Y[i]], Ft[Y[i]], H[X[i]]));
} else {
n++;
add(St[n], H[n]);
}
}
return 0;
}
Compilation message
klasika.cpp: In function 'int main()':
klasika.cpp:97:24: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
97 | printf("%lld\n", get(St[Y[i]], Ft[Y[i]], H[X[i]]));
| ~~~^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| | |
| | int
| long long int
| %d
klasika.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
80 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
95 ms |
98924 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
95 ms |
98924 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
751 ms |
326892 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
95 ms |
98924 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
