Submission #519706

#	Time	Username	Problem	Language	Result	Execution time	Memory
519706		KoD	Klasika (COCI20_klasika)	C++17	110 / 110	2610 ms	465064 KiB

klasika

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

constexpr int LOG = 30;

struct Trie {
    struct Node {
        array<int, 2> child;
        std::set<int> set;
        Node() { child.fill(-1); }
    };
    int root;
    vector<Node> node;
    Trie() { root = add_node(); }
    int add_node() {
        node.emplace_back();
        return node.size() - 1;
    }
    void insert(const int i, const int x) {
        int u = root;
        for (int d = LOG - 1; d >= 0; --d) {
            const int k = x >> d & 1;
            if (node[u].child[k] == -1) {
                node[u].child[k] = add_node();
            }
            u = node[u].child[k];
            node[u].set.insert(i);
        }
    }
    int max(const int l, const int r, const int x) const {
        int u = root, ret = 0;
        for (int d = LOG - 1; d >= 0; --d) {
            const int k = x >> d & 1;
            const int good = node[u].child[k ^ 1];
            const int bad = node[u].child[k];
            if (good == -1) {
                u = bad;
            } else if (auto itr = node[good].set.lower_bound(l); itr != node[good].set.end() and *itr < r) {
                u = good;
                ret += 1 << d;
            } else {
                u = bad;
            }
        }
        return ret;
    }
};

template <class F> struct RecLambda : private F {
    explicit RecLambda(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int Q;
    std::cin >> Q;
    int N = 1;
    vector<int> value(N);
    vector<vector<int>> graph(N);
    vector<pair<int, int>> query(Q);
    for (auto& [a, b] : query) {
        std::string s;
        std::cin >> s;
        if (s == "Add") {
            int x, y;
            std::cin >> x >> y;
            const int u = N++;
            value.push_back(y);
            graph.emplace_back();
            graph[x - 1].push_back(u);
            a = u, b = -1;
        } else {
            std::cin >> a >> b;
            a -= 1, b -= 1;
        }
    }
    vector<int> in(N), out(N);
    int stamp = 0;
    RecLambda([&](auto&& dfs, const int u, const int p) -> void {
        in[u] = stamp++;
        value[u] ^= value[p];
        for (const int v : graph[u]) {
            dfs(v, u);
        }
        out[u] = stamp;
    })(0, 0);
    Trie trie;
    trie.insert(in[0], value[0]);
    for (const auto& [a, b] : query) {
        if (b == -1) {
            trie.insert(in[a], value[a]);
        } else {
            std::cout << trie.max(in[b], out[b], value[a]) << '\n';
        }
    }
    return 0;
}

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