oj.uz

Submission #1049313

# Submission time Handle Problem Language Result Execution time Memory
1049313 2024-08-08T16:18:12 Z thangdz2k7 Klasika (COCI20_klasika) C++17
0 / 110
 38 ms 36168 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];
    vector <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.push_back(st[u]);
    }
}

bool mid(vector <int> &h, int l, int r){
    int it = lower_bound(h.begin(), h.end(), l) - h.begin();
    return it < int(h.size()) && h[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);
    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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 29532 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 29532 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 36168 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 29532 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -