Submission #1017497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017497		vjudge1	Klasika (COCI20_klasika)	C++17	66 / 110	489 ms	191060 KiB

klasika

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

typedef long long ll;

const ll N = 2e5 + 10, LG = 31;
ll q, n = 2, par[N][LG], sp[N][LG], h[N];
ll sz = 1, nxt[N * 31][2];

int val[N], res, cur;
bool in_sub[2005][2005];
vector<pair<int, int>> g[N];

void dfs(int v, int b, int p = -1){
    if (in_sub[b][v])
        res = max(res, cur);
    for (auto [w, u] : g[v]){
        if (u == p) continue;
        cur ^= w;
        dfs(u, b, v);
        cur ^= w;
    }
}


void add(ll x){
    ll cur = 0;
    for (ll i = 30; i >= 0; i --){
        int b = (((1ll << i) & x) > 0);
        if (nxt[cur][b] == -1)
            nxt[cur][b] = sz++;
        cur = nxt[cur][b];
    }
}

ll get(ll x){
    ll cur = 0;
    ll res = 0;
    for (ll i = 30; i >= 0; i --){
        int b = (((1ll << i) & x) > 0);
        if (nxt[cur][1 - b] != -1){
            cur = nxt[cur][1 - b];
            res |= (1ll << i);
        }
        else
            cur = nxt[cur][b];
    }
    return res;
}

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

    memset(par, -1, sizeof par);
    memset(nxt, -1, sizeof nxt);

    cin >> q;

    if (q <= 2000){
        int n = 1;
        in_sub[1][1] = 1;
        while (q--){
            string s;
            cin >> s;

            if (s[0] == 'A'){
                int x, y;
                cin >> x >> y;

                int v = ++n;
                par[v][0] = x;
                val[v] = y;

                int p = v;
                while (p != -1){
                    in_sub[p][v] = 1;
                    p = par[p][0];
                }

                g[x].push_back({y, v});
                g[v].push_back({y, x});
            }
            else{
                int a, b;
                cin >> a >> b;

                res = 0;
                cur = 0;
                dfs(a, b);

                cout << res << endl;
            }
        }

        return 0;
    }

    add(0);
    while (q--){
        string s;
        cin >> s;

        if (s == "Add"){
            ll x, y;
            cin >> x >> y;

            par[n][0] = x;
            sp[n][0] = y;

            for (ll i = 1; i < LG; i ++){
                if (par[n][i - 1] == -1) continue;
                par[n][i] = par[par[n][i - 1]][i - 1];
                sp[n][i] = sp[n][i - 1] ^ sp[par[n][i - 1]][i - 1];
            }
            h[n] = h[x] + 1;

            ll v = n;
            ll d = h[v] - h[1];
            ll val = 0;
            for (ll i = 0; i < LG; i ++){
                if ((1ll << i) & d){
                    val ^= sp[v][i];
                    v = par[v][i];
                }
            }

            add(val);
            // cout << "adding " << val << " in trie" << endl;

            n++;
        }
        else{
            ll a, b;
            cin >> a >> b;

            ll v = a;
            ll d = h[v] - h[1];
            ll val = 0;
            for (ll i = 0; i < LG; i ++){
                if ((1ll << i) & d){
                    val ^= sp[v][i];
                    v = par[v][i];
                }
            }

            // cout << "getting from " << val << endl; 
            cout << get(val) << endl;
        }
    }
}

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