oj.uz

Submission #1049328

# Submission time Handle Problem Language Result Execution time Memory
1049328 2024-08-08T16:33:05 Z thangdz2k7 Klasika (COCI20_klasika) C++17
110 / 110
 1526 ms 437684 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;
const int LG = 30;

int q, n = 1, w[N], x[N], y[N];
string t[N];
vector <int> adj[N];
int st[N], ed[N], cnt = 0;

void dfs(int u){
    st[u] = ++ cnt;
    for (int v : adj[u]){
        w[v] ^= w[u];
        dfs(v);
    }
    ed[u] = cnt;
}

struct Node{
    Node *child[2];
    set <int> idx;

    Node(){
        child[0] = NULL; child[1] = NULL;
        idx = {};
    }
} *root = new Node();

void add(int u){
    Node *p = root;
    for (int i = LG; i >= 0; -- i){
        int b = (w[u] >> i) & 1;
        if (p -> child[b] == NULL) p -> child[b] = new Node();
        p = p -> child[b];
        p -> idx.insert(st[u]);
    }
}

bool mid(set <int> &h, int l, int r){
    auto it = h.lower_bound(l);
    return it != h.end() && *it <= r;
}

int get(int u, int l, int r){
    int ans = 0;
    Node *p = root;
    for (int i = LG; i >= 0; -- i){
        int b = (u >> i) & 1;
        if (p -> child[1 ^ b] != NULL && mid(p -> child[1 ^ b] -> idx, l, r)) {
            ans += (1 << i);
            p = p -> child[1 ^ b];
        }
        else p = p -> child[b];
    }
    return ans;
}

void solve(){
    cin >> q;
    for (int i = 1; i <= q; ++ i){
        cin >> t[i] >> x[i] >> y[i];
        if (t[i] == "Add"){
            ++ n;
            adj[x[i]].push_back(n);
            w[n] = y[i]; x[i] = n;
        }
    }
    dfs(1); add(1);
    for (int i = 1; i <= q; ++ i){
        if (t[i] == "Add") add(x[i]);
        else cout << get(w[x[i]], st[y[i]], ed[y[i]]) << '\n';
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();

    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2 ms 15196 KB Output is correct
4 Correct 2 ms 15196 KB Output is correct
5 Correct 2 ms 14940 KB Output is correct
6 Correct 2 ms 14940 KB Output is correct
7 Correct 2 ms 15208 KB Output is correct
8 Correct 2 ms 15196 KB Output is correct
9 Correct 2 ms 14940 KB Output is correct
10 Correct 2 ms 14940 KB Output is correct
11 Correct 2 ms 15196 KB Output is correct
12 Correct 2 ms 15192 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2 ms 15196 KB Output is correct
4 Correct 2 ms 15196 KB Output is correct
5 Correct 2 ms 14940 KB Output is correct
6 Correct 2 ms 14940 KB Output is correct
7 Correct 2 ms 15208 KB Output is correct
8 Correct 2 ms 15196 KB Output is correct
9 Correct 2 ms 14940 KB Output is correct
10 Correct 2 ms 14940 KB Output is correct
11 Correct 2 ms 15196 KB Output is correct
12 Correct 2 ms 15192 KB Output is correct
13 Correct 4 ms 16220 KB Output is correct
14 Correct 4 ms 17348 KB Output is correct
15 Correct 5 ms 18524 KB Output is correct
16 Correct 6 ms 19708 KB Output is correct
17 Correct 4 ms 15960 KB Output is correct
18 Correct 5 ms 17244 KB Output is correct
19 Correct 6 ms 18524 KB Output is correct
20 Correct 7 ms 19548 KB Output is correct
21 Correct 4 ms 15964 KB Output is correct
22 Correct 5 ms 17244 KB Output is correct
23 Correct 6 ms 18536 KB Output is correct
24 Correct 6 ms 19548 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 127060 KB Output is correct
2 Correct 606 ms 234876 KB Output is correct
3 Correct 847 ms 335804 KB Output is correct
4 Correct 1076 ms 437072 KB Output is correct
5 Correct 337 ms 127568 KB Output is correct
6 Correct 634 ms 230480 KB Output is correct
7 Correct 921 ms 329044 KB Output is correct
8 Correct 1239 ms 427860 KB Output is correct
9 Correct 333 ms 127316 KB Output is correct
10 Correct 590 ms 231504 KB Output is correct
11 Correct 850 ms 331768 KB Output is correct
12 Correct 1132 ms 430208 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2 ms 15196 KB Output is correct
4 Correct 2 ms 15196 KB Output is correct
5 Correct 2 ms 14940 KB Output is correct
6 Correct 2 ms 14940 KB Output is correct
7 Correct 2 ms 15208 KB Output is correct
8 Correct 2 ms 15196 KB Output is correct
9 Correct 2 ms 14940 KB Output is correct
10 Correct 2 ms 14940 KB Output is correct
11 Correct 2 ms 15196 KB Output is correct
12 Correct 2 ms 15192 KB Output is correct
13 Correct 4 ms 16220 KB Output is correct
14 Correct 4 ms 17348 KB Output is correct
15 Correct 5 ms 18524 KB Output is correct
16 Correct 6 ms 19708 KB Output is correct
17 Correct 4 ms 15960 KB Output is correct
18 Correct 5 ms 17244 KB Output is correct
19 Correct 6 ms 18524 KB Output is correct
20 Correct 7 ms 19548 KB Output is correct
21 Correct 4 ms 15964 KB Output is correct
22 Correct 5 ms 17244 KB Output is correct
23 Correct 6 ms 18536 KB Output is correct
24 Correct 6 ms 19548 KB Output is correct
25 Correct 336 ms 127060 KB Output is correct
26 Correct 606 ms 234876 KB Output is correct
27 Correct 847 ms 335804 KB Output is correct
28 Correct 1076 ms 437072 KB Output is correct
29 Correct 337 ms 127568 KB Output is correct
30 Correct 634 ms 230480 KB Output is correct
31 Correct 921 ms 329044 KB Output is correct
32 Correct 1239 ms 427860 KB Output is correct
33 Correct 333 ms 127316 KB Output is correct
34 Correct 590 ms 231504 KB Output is correct
35 Correct 850 ms 331768 KB Output is correct
36 Correct 1132 ms 430208 KB Output is correct
37 Correct 552 ms 130944 KB Output is correct
38 Correct 830 ms 234828 KB Output is correct
39 Correct 1064 ms 338480 KB Output is correct
40 Correct 1197 ms 437684 KB Output is correct
41 Correct 623 ms 128100 KB Output is correct
42 Correct 930 ms 230528 KB Output is correct
43 Correct 1205 ms 329408 KB Output is correct
44 Correct 1526 ms 427268 KB Output is correct
45 Correct 663 ms 127828 KB Output is correct
46 Correct 1000 ms 231672 KB Output is correct
47 Correct 1202 ms 330328 KB Output is correct
48 Correct 1327 ms 430160 KB Output is correct