Submission #519686

#	Time	Username	Problem	Language	Result	Execution time	Memory
519686		KoD	Klasika (COCI20_klasika)	C++17	33 / 110	901 ms	524292 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;
        Node() { child.fill(-1); }
    };
    static inline vector<Node> node;
    static int add_node() {
        node.emplace_back();
        return node.size() - 1;
    }
    int root;
    Trie() : root(-1) {}
    void insert(const int x) {
        if (root == -1) {
            root = add_node();
        }
        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];
        }
    }
    int max(const int x) const {
        if (root == -1) {
            return 0;
        }
        int u = root, ret = 0;
        for (int d = LOG - 1; d >= 0; --d) {
            const int k = x >> d & 1;
            if (node[u].child[k ^ 1] == -1) {
                u = node[u].child[k];
            } else {
                u = node[u].child[k ^ 1];
                ret |= 1 << d;
            }
        }
        return ret;
    }
};

struct SegTree {
    int size;
    vector<Trie> data;
    SegTree(const int n) : size(n), data(2 * n, Trie()) {}
    void add(int k, const int x) {
        k += size;
        while (k > 0) {
            data[k].insert(x);
            k >>= 1;
        }
    }
    int max(int l, int r, const int x) const {
        int ret = 0;
        l += size, r += size;
        while (l < r) {
            if (l & 1) ret = std::max(ret, data[l++].max(x));
            if (r & 1) ret = std::max(ret, data[--r].max(x));
            l >>= 1, r >>= 1;
        }
        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);
    SegTree seg(N);
    seg.add(in[0], value[0]);
    for (const auto& [a, b] : query) {
        if (b == -1) {
            seg.add(in[a], value[a]);
        } else {
            std::cout << seg.max(in[b], out[b], value[a]) << '\n';
        }
    }
    return 0;
}

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