Submission #1125186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125186		Zero_OP	Klasika (COCI20_klasika)	C++17	33 / 110	5095 ms	61108 KiB

klasika

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

using namespace std;

const int MAXNODES = (2e5) * 30;
int used = 0, nxt[2][MAXNODES], mn[MAXNODES];

void insert(int x, int y){
    int nd = 0;
    for(int i = 29; i >= 0; --i){
        int t = (x >> i & 1);
        if(!nxt[t][nd]){
            nxt[t][nd] = ++used;
            mn[used] = y;
        }

        nd = nxt[t][nd];
        mn[nd] = min(mn[nd], y);
    }
}

int max_xor(int x, int y){ // <= y
    int ans = 0, nd = 0;
    for(int i = 29; i >= 0; --i){
        int t = (x >> i & 1);
        if(nxt[t ^ 1][nd] > 0 && mn[nxt[t ^ 1][nd]] <= y){
            ans |= (1 << i);
            nd = nxt[t ^ 1][nd];
        } else{
            nd = nxt[t][nd];
        }
    }
    return ans;
}

void reset(){
    for(int i = 0; i <= used; ++i) nxt[0][i] = nxt[1][i] = 0; used = 0;
}

const int MAX = 2e5 + 5;

int N, Q, timer_dfs, val[MAX], t[MAX], tin[MAX], tout[MAX], ans[MAX], tour[MAX], sz[MAX], heavy[MAX];
vector<pair<int, int>> adj[MAX];
vector<tuple<int, int, int>> queries[MAX];

void dfs(int u){
    tour[tin[u] = ++timer_dfs] = u;
    sz[u] = 1;
    for(auto [v, w] : adj[u]){
        val[v] = val[u] ^ w;
        dfs(v);
        if(heavy[u] == 0 || sz[heavy[u]] < sz[v]) heavy[u] = v;
    }
    tout[u] = timer_dfs;
}

void sack(int u, bool keep){
    for(auto [v, w] : adj[u]) if(v != heavy[u]){
        sack(v, false);
    }

    if(heavy[u]){
        sack(heavy[u], true);
    }

    insert(val[u], t[u]);
    for(auto [v, w] : adj[u]) if(v != heavy[u]){
        for(int i = tin[v]; i <= tout[v]; ++i){
            insert(val[tour[i]], t[tour[i]]);
        }
    }

    for(auto [v, t, id] : queries[u]){
        ans[id] = max_xor(val[v], t);
    }

    queries[u].clear();
    if(!keep) reset();
}

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

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    cin >> Q;
    N = 1;

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

    dfs(1);
    sack(1, true);

    for(int i = 0; i < asks; ++i){
        cout << ans[i] << '\n';
    }

    return 0;
}

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