Submission #1164450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164450		ahmedhali107	Klasika (COCI20_klasika)	C++20	110 / 110	297 ms	151736 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 & (1 << 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 & (1 << 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;
    }
};

using trie = xortrie<int, 30>;

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);
    auto dfs = [&](auto &&dfs, int u, int p) -> trie {
        trie me;
        me.insert(val[u].first, val[u].second);
        for (int v: g[u]) {
            if (v == p) continue;
            trie child = dfs(dfs, v, u);
            if (child.vals.size() > me.vals.size()) {
                swap(child, me);
            }
            for (auto &[x, t]: child.vals) {
                me.insert(x, t);
            }
        }
        for (auto &[x, t]: qs[u]) {
            ans[t] = me.max(x, t);
        }
        return me;
    };
    auto _ = dfs(dfs, 0, 0);
    for (auto &i: ans) if (~i) cout << 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