#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#endif
#define f first
#define s second
template<class T> using V = vector<T>;
using vi = V<int>;
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define pb push_back
#define lb lower_bound
#define ub upper_bound
template<class T> int lwb(V<T>& a, const T& b) { return lb(all(a),b)-begin(a); }
template<class T> int upb(V<T>& a, const T& b) { return ub(all(a),b)-begin(a); }
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a=b, true : false; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a=b, true : false; }
constexpr int p2(int x) { return (int)1 << x; }
const int LOGX = 30, MAX_N = 2e5, MAX_NODES = 1e6;
struct Node {
int sons[2];
set<int> tins;
Node() {
sons[0] = sons[1] = -1;
tins = {};
}
} trie[MAX_NODES];
int trie_siz = 1;
void add_str(int str, int time) {
int u = 0;
for (int i = LOGX-1; i >= 0; i--) {
trie[u].tins.insert(time);
bool nxt = str&p2(i);
int& c = trie[u].sons[nxt];
if (c != -1) {
u = c;
} else {
u = c = trie_siz++;
}
}
trie[u].tins.insert(time);
}
int best_match(int pattern, int l, int r) {
int match = 0;
int u = 0;
for (int i = LOGX-1; i >= 0; i--) {
bool nxt = !(pattern & p2(i));
int c = trie[u].sons[nxt];
if (c != -1 && trie[c].tins.lb(l) != trie[c].tins.end() && *trie[c].tins.lb(l) < r) {
u = c;
match += p2(i)*nxt;
} else {
u = trie[u].sons[1-nxt];
match += p2(i)*(1-nxt);
}
}
return match;
}
int timer;
vi tin, tout, x;
V<V<array<int, 2>>> sons;
void dfs(int u) {
tin[u] = timer++;
for (auto [v, w] : sons[u]) {
x[v] = x[u]^w;
dfs(v);
}
tout[u] = timer;
}
void solve() {
int q; cin >> q;
int n = 1;
V<array<int, 3>> queries;
for (int i = 0; i < q; i++) {
string typ; cin >> typ;
if (typ == "Add") {
int u, w; cin >> u >> w; u--;
queries.pb({0, n, -1});
sons.resize(n+1);
sons[u].pb({n++, w});
} else {
int a, b; cin >> a >> b; a--; b--;
queries.pb({1, a, b});
}
}
tin.resize(n);
tout.resize(n);
x.resize(n);
dfs(0);
add_str(0, 0);
for (int i = 0; i < q; i++) {
if (queries[i][0] == 0) {
auto [_, u, __] = queries[i];
add_str(x[u], tin[u]);
} else {
auto [_, a, b] = queries[i];
cout << (x[a]^best_match(x[a], tin[b], tout[b])) << '\n';
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
solve();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
33 ms |
55120 KB |
Output is correct |
2 |
Correct |
29 ms |
55120 KB |
Output is correct |
3 |
Correct |
32 ms |
55384 KB |
Output is correct |
4 |
Correct |
32 ms |
55384 KB |
Output is correct |
5 |
Correct |
30 ms |
55132 KB |
Output is correct |
6 |
Correct |
32 ms |
55128 KB |
Output is correct |
7 |
Correct |
36 ms |
55376 KB |
Output is correct |
8 |
Correct |
34 ms |
55372 KB |
Output is correct |
9 |
Correct |
31 ms |
55128 KB |
Output is correct |
10 |
Correct |
32 ms |
55380 KB |
Output is correct |
11 |
Correct |
32 ms |
55388 KB |
Output is correct |
12 |
Correct |
33 ms |
55380 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
33 ms |
55120 KB |
Output is correct |
2 |
Correct |
29 ms |
55120 KB |
Output is correct |
3 |
Correct |
32 ms |
55384 KB |
Output is correct |
4 |
Correct |
32 ms |
55384 KB |
Output is correct |
5 |
Correct |
30 ms |
55132 KB |
Output is correct |
6 |
Correct |
32 ms |
55128 KB |
Output is correct |
7 |
Correct |
36 ms |
55376 KB |
Output is correct |
8 |
Correct |
34 ms |
55372 KB |
Output is correct |
9 |
Correct |
31 ms |
55128 KB |
Output is correct |
10 |
Correct |
32 ms |
55380 KB |
Output is correct |
11 |
Correct |
32 ms |
55388 KB |
Output is correct |
12 |
Correct |
33 ms |
55380 KB |
Output is correct |
13 |
Correct |
34 ms |
55888 KB |
Output is correct |
14 |
Correct |
41 ms |
56400 KB |
Output is correct |
15 |
Correct |
33 ms |
57180 KB |
Output is correct |
16 |
Correct |
36 ms |
57684 KB |
Output is correct |
17 |
Correct |
33 ms |
55888 KB |
Output is correct |
18 |
Correct |
35 ms |
56404 KB |
Output is correct |
19 |
Correct |
37 ms |
56916 KB |
Output is correct |
20 |
Correct |
37 ms |
57636 KB |
Output is correct |
21 |
Correct |
34 ms |
55896 KB |
Output is correct |
22 |
Correct |
35 ms |
56340 KB |
Output is correct |
23 |
Correct |
38 ms |
56916 KB |
Output is correct |
24 |
Correct |
36 ms |
57464 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
617 ms |
123392 KB |
Output is correct |
2 |
Runtime error |
793 ms |
333244 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
33 ms |
55120 KB |
Output is correct |
2 |
Correct |
29 ms |
55120 KB |
Output is correct |
3 |
Correct |
32 ms |
55384 KB |
Output is correct |
4 |
Correct |
32 ms |
55384 KB |
Output is correct |
5 |
Correct |
30 ms |
55132 KB |
Output is correct |
6 |
Correct |
32 ms |
55128 KB |
Output is correct |
7 |
Correct |
36 ms |
55376 KB |
Output is correct |
8 |
Correct |
34 ms |
55372 KB |
Output is correct |
9 |
Correct |
31 ms |
55128 KB |
Output is correct |
10 |
Correct |
32 ms |
55380 KB |
Output is correct |
11 |
Correct |
32 ms |
55388 KB |
Output is correct |
12 |
Correct |
33 ms |
55380 KB |
Output is correct |
13 |
Correct |
34 ms |
55888 KB |
Output is correct |
14 |
Correct |
41 ms |
56400 KB |
Output is correct |
15 |
Correct |
33 ms |
57180 KB |
Output is correct |
16 |
Correct |
36 ms |
57684 KB |
Output is correct |
17 |
Correct |
33 ms |
55888 KB |
Output is correct |
18 |
Correct |
35 ms |
56404 KB |
Output is correct |
19 |
Correct |
37 ms |
56916 KB |
Output is correct |
20 |
Correct |
37 ms |
57636 KB |
Output is correct |
21 |
Correct |
34 ms |
55896 KB |
Output is correct |
22 |
Correct |
35 ms |
56340 KB |
Output is correct |
23 |
Correct |
38 ms |
56916 KB |
Output is correct |
24 |
Correct |
36 ms |
57464 KB |
Output is correct |
25 |
Correct |
617 ms |
123392 KB |
Output is correct |
26 |
Runtime error |
793 ms |
333244 KB |
Execution killed with signal 11 |
27 |
Halted |
0 ms |
0 KB |
- |