Submission #1125175

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125175		Zero_OP	Klasika (COCI20_klasika)	C++20	110 / 110	3145 ms	468452 KiB

klasika

//expected memory : ~ 183 mb
#include <bits/stdc++.h>

using namespace std;

struct Trie{
    struct node{
        int next[2];
        set<int> st;

        node() : st() {
            next[0] = next[1] = -1;
        }

        bool check(int l, int r){
            return st.upper_bound(r) != st.lower_bound(l);
        }
    };

    vector<node> nodes;

    Trie() : nodes() {
        nodes.emplace_back(node());
    }

    void insert(int x, int id){
        int u = 0;
        for(int i = 29; i >= 0; --i){
            bool t = (x >> i & 1);
            if(nodes[u].next[t] == -1){
                nodes[u].next[t] = (int)nodes.size();
                nodes.emplace_back(node());
            }

            u = nodes[u].next[t];
            nodes[u].st.insert(id);
        }
    }

    int max_xor(int x, int l, int r){
        int ans = 0, u = 0;
        for(int i = 29; i >= 0; --i){
            int t = (x >> i & 1);
            if((nodes[u].next[t ^ 1] != -1) && (nodes[nodes[u].next[t ^ 1]].check(l, r))){
                ans |= (1 << i);
                u = nodes[u].next[t ^ 1];
            } else{
                assert(nodes[u].next[t] != -1);
                u = nodes[u].next[t];
            }
        }
        return ans;
    }
};

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    int Q;
    cin >> Q;
    int N = 1;

    vector<vector<pair<int, int>>> adj;
    adj.emplace_back();

    vector<tuple<int, int, int>> queries;
    for(int i = 0; i < Q; ++i){
        string t;
        int u, v;
        cin >> t >> u >> v;
        if(t[0] == 'A'){
            --u;
            adj.emplace_back();
            adj[u].emplace_back(N++, v);
            queries.emplace_back(0, N - 1, -1);
        } else{
            --u, --v;
            queries.emplace_back(1, u, v);
        }
    }

    int timer_dfs = 0;
    vector<int> vl(N), tin(N), tout(N);

    function<void(int)> dfs = [&](int u){
        tin[u] = ++timer_dfs;
        for(auto [v, w] : adj[u]){
            vl[v] = vl[u] ^ w;
            dfs(v);
        }
        tout[u] = timer_dfs;
    };

    dfs(0);
    Trie tr;

    tr.insert(0, tin[0]);
    for(auto [type, u, v] : queries){
        if(type == 0){
            tr.insert(vl[u], tin[u]);
        } else{
            cout << tr.max_xor(vl[u], tin[v], tout[v]) << '\n';
        }
    }

    return 0;
}

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