Submission #1087748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087748		MinhKien	Klasika (COCI20_klasika)	C++17	0 / 110	411 ms	128544 KiB

klasika

#include <iostream>
#include <string>
#include <vector>
#include <set>

using namespace std;

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

int q, x[N];

vector <int> v[N];
int num[N], last[N], cnt, k = 1;
void dfs(int s) {
    num[s] = last[s] = ++cnt;

    for (int z: v[s]) {
        dfs(z);
        last[s] = last[z];
    }
}

struct Trie {
    struct node {
        node *child[2];
        set <int> s;

        node () {
            child[0] = child[1] = nullptr;
            s.clear();
        }
    };

    node *root;
    Trie () {
        root = new node ();
    }

    void add_num(int val, int Num) {
        node *cur = root;
        for (int i = LG; i >= 0; --i) {
            int c = val >> i & 1;
            if (cur->child[c] == nullptr) cur->child[c] = new node();
            cur = cur->child[c];
            cur->s.insert(Num);
        }
    }

    int solve(int val, int b) {
        int ans = 0;
        node *cur = root;
        set <int> :: iterator it;

        for (int i = LG; i >= 0; --i) {
            int c = (val >> i & 1) ^ 1;

            bool check = false;
            if (cur->child[c] != nullptr) {
                it = cur->child[c]->s.lower_bound(num[b]);
                if (it != cur->child[c]->s.end() && *it <= last[b]) {
                    check = true;
                    ans |= (1 << i);
                    cur = cur->child[c];
                }
            }

            if (!check) {
                if (cur->child[c ^ 1] != nullptr) {
                    it = cur->child[c ^ 1]->s.lower_bound(num[b]);
                    if (it != cur->child[c ^ 1]->s.end() && *it <= last[b]) {
                        cur = cur->child[c ^ 1];
                        check = true;
                    }
                }
            }

            if (!check) return ans;
        }

        return ans;
    }
} T;

struct query {
    string t;
    int a, b;
} Q[N];

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

    cin >> q;
    for (int i = 1; i <= q; ++i) {
        cin >> Q[i].t >> Q[i].a >> Q[i].b;

        if (Q[i].t == "Add") {
            v[Q[i].a].push_back(++k);
        }
    }

    dfs(1);

    k = 1;
    for (int i = 1; i <= q; ++i) {
        if (Q[i].t == "Add") {
            x[++k] = x[Q[i].a] ^ Q[i].b;
            T.add_num(x[k], num[k]);
        } else {
            cout << T.solve(x[Q[i].a], Q[i].b) << "\n";
        }
    }

    return 0;
}

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