Submission #1164492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164492		gohary	Klasika (COCI20_klasika)	C++20	110 / 110	317 ms	149004 KiB

klasika

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

template <class T, int bits> struct xortrie {
    vector<array<int, 2>> trie = {{0, 0}}, vals;
    vector<int> mn = {0};

    xortrie() {}

    void insert(T val, int time) {
        int node = 0;
        vals.push_back({val, time});
        for (int i = bits - 1; i >= 0; i--) {
            int j = (val & (1ll << i) ? 1 : 0);
            if (trie[node][j] == 0) {
                trie[node][j] = trie.size();
                trie.push_back({0, 0});
                mn.push_back(time);
            }
            node = trie[node][j];
            mn[node] = min(mn[node], time);
        }
    }


    T max(T val, int time) {
        T ans = 0;
        int node = 0;
        for (int i = bits - 1; i >= 0; i--) {
            int j = (val & (1ll << i) ? 0 : 1);
            if (trie[node][j] && mn[trie[node][j]] <= time) {
                ans |= (1ll << i);
                node = trie[node][j];
            } else if (mn[trie[node][j ^ 1]] <= time) {
                node = trie[node][j ^ 1];
            } else {
                break;
            }
        }
        return ans;
    }
};

void solve() {
    int q;
    cin >> q;
    vector<vector<int>> g(1);
    vector<vector<pair<int, int>>> qs(1);
    vector<pair<int, int>> val{{0, 0}};
    for (int i = 1; i <= q; i++) {
        string qt;
        int x, y;
        cin >> qt >> x >> y, x--;
        if (qt[0] == 'A') {
            g[x].push_back(g.size());
            g.emplace_back();
            val.emplace_back(val[x].first ^ y, i);
            qs.emplace_back();
        } else {
            y--;
            qs[y].emplace_back(val[x].first, i);
        }
    }
    vector<int> ans(q + 1, -1);
    function<xortrie<int, 31>(int)> dfs = [&](int v) {
        xortrie<int, 31> tv;
        tv.insert(val[v].first, val[v].second);
        for (int u : g[v]) {
            auto tu = dfs(u);
            if (tv.vals.size() < tu.vals.size()) swap(tu, tv);
            for (const auto& [x, time] : tu.vals) tv.insert(x, time);
        }
        for (const auto& [x, time] : qs[v]) ans[time] = tv.max(x, time);
        return tv;
    };
    dfs(0);
    for (int i = 1; i <= q; i++) {
        if (~ans[i]) cout << ans[i] << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

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