Submission #487575

#	Time	Username	Problem	Language	Result	Execution time	Memory
487575		KazamaHoang	Klasika (COCI20_klasika)	C++14	110 / 110	2102 ms	424280 KiB

klasika

#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

struct Node {
    Node* nxt[2];
    set<int> s;
};

Node* create() {
    Node* res = new Node();
    for (int i = 0; i < 2; ++ i)
        res->nxt[i] = NULL;
    res->s.clear();
    return res;
}
    
int n = 1;
int numQuery;
pair<bool, pair<int, int>> qry[200005];
vector<int> adj[200005];
int in[200005], out[200005], timer = 0, Xor[200005];

Node* root = create();

inline int getbit(int x, int i) {
    return x >> i & 1;
}

void dfs(int u, int par = -1) {
    in[u] = ++ timer;
    for (int& v : adj[u])
        if (v != par) dfs(v, u);
    out[u] = timer;
}

void trie_insert(int x, int pos) {
    Node* tmp = root;
    for (int i = 29; i >= 0; -- i) {
        int c = getbit(x, i);
        if (root->nxt[c] == NULL) 
            root->nxt[c] = create();
        root = root->nxt[c];
        root->s.insert(pos);
    }
    root = tmp;
}

int trie_get(int x, int u) {
    int res = 0;
    Node* tmp = root;
    for (int i = 29; i >= 0; -- i) {
        int lf = 0, rt = 1;
        if (getbit(x, i)) swap(lf, rt);
        if (root->nxt[rt] == NULL) { 
            root = root->nxt[lf];
        } else {

            auto it = root->nxt[rt]->s.lower_bound(in[u]);
            if (it != root->nxt[rt]->s.end() && *it <= out[u]) {
                res += (1 << i);
                root = root->nxt[rt];
            } else {
                root = root->nxt[lf];
            }
        }
    }
    root = tmp;
    return res;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> numQuery;
    for (int i = 1; i <= numQuery; ++ i) {
        string op;
        cin >> op >> qry[i].S.F >> qry[i].S.S;
        if (op == "Add") {
            qry[i].F = 0;
            int u = qry[i].S.F;
            int w = qry[i].S.S;
            int v = ++ n;
            Xor[v] = Xor[u] ^ w;
            adj[u].push_back(v);
            qry[i].S.F = v;
        } else qry[i].F = 1;
    }
    dfs(1);
    trie_insert(0, in[1]);
    for (int i = 1; i <= numQuery; ++ i) {
        if (!qry[i].F) {
            trie_insert(Xor[qry[i].S.F], in[qry[i].S.F]);
        } else {
            cout << trie_get(Xor[qry[i].S.F], qry[i].S.S) << "\n";
        }
    }
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 33 / 33
• Subtask 4: 44 / 44