제출 #1049313

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1049313		thangdz2k7	Klasika (COCI20_klasika)	C++17	0 / 110	38 ms	36168 KiB

klasika

#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
• Subtask 2: 0 / 22
• Subtask 3: 0 / 33
• Subtask 4: 0 / 44