Submission #588542

#	Time	Username	Problem	Language	Result	Execution time	Memory
588542		leeh18	Klasika (COCI20_klasika)	C++17	110 / 110	2789 ms	428992 KiB

klasika

#include <bits/stdc++.h>
using namespace std;

struct graph {
    int n, timer;
    vector<vector<pair<int, int>>> adj;
    vector<int> dist, tin, tout;
    graph(int n_) : n(n_), timer(0), adj(n), dist(n), tin(n), tout(n) {}
    void add_edge(int parent, int node, int weight) {
        adj[parent].push_back({node, weight});
    }
    void dfs(int u = 0) {
        tin[u] = timer++;
        for (auto [v, w] : adj[u]) {
            dist[v] = dist[u] ^ w;
            dfs(v);
        }
        tout[u] = timer++;
    }
};

struct trie_node {
    array<unique_ptr<trie_node>, 2> children;
    set<int> s;
    void insert(int x, int tin, int pos = 30) {
        if (pos < 0) return;
        int bit = (x >> pos) & 1;
        if (children[bit] == nullptr) {
            children[bit] = make_unique<trie_node>();
        }
        children[bit]->s.insert(tin);
        children[bit]->insert(x, tin, pos-1);
    }
    bool check(int bit, int tin, int tout) {
        if (children[bit] == nullptr) return false;
        const auto &cs = children[bit]->s;
        auto lower_it = cs.lower_bound(tin);
        auto upper_it = cs.upper_bound(tout);
        return lower_it != upper_it;
    }
    int max_xor(int x, int tin, int tout, int pos = 30) {
        if (pos < 0) return 0;
        int ret = 0;
        int bit = (x >> pos) & 1;
        if (check(bit^1, tin, tout)) {
            ret = children[bit^1]->max_xor(x, tin, tout, pos-1);
            ret |= (1 << pos);
        } else {
            ret = children[bit]->max_xor(x, tin, tout, pos-1);
        }
        return ret;
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int Q;
    cin >> Q;
    vector<tuple<int, int, int>> qs(Q);
    int cnt = 1;
    for (auto &[t, a, b] : qs) {
        string s;
        cin >> s >> a >> b;
        if (s == "Add") {
            t = 1;
            ++cnt;
            --a;
        } else {
            t = 2;
            --a;
            --b;
        }
    }
    graph g(cnt);
    int id = 0;
    for (auto &[t, a, b] : qs) {
        if (t == 1) {
            ++id;
            g.add_edge(a, id, b);
            b = id;
        }
    }
    g.dfs();
    trie_node trie;
    trie.insert(0, g.tin[0]);
    for (auto [t, a, b] : qs) {
        if (t == 1) {
            trie.insert(g.dist[b], g.tin[b]);
        } else {
            auto ans = trie.max_xor(g.dist[a], g.tin[b], g.tout[b]);
            cout << ans << '\n';
        }
    }
}

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