Submission #1276014

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276014		papaulo	Klasika (COCI20_klasika)	C++20	110 / 110	647 ms	315684 KiB

klasika

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

#define MAXQ 200200
vector<int> trie[MAXQ][2];
vector<int> mn[MAXQ];
int id[MAXQ];
vector<int> chi[MAXQ];
int t=1;
int val[MAXQ];
vector<pair<int, pair<int, int>>> qs[MAXQ];
vector<pair<int, int>> vec[MAXQ];
int ans[MAXQ];
int sz[MAXQ];

void insert(int t, int v, int tmp) {
    int n=0;
    for(int i=31;i>=0;i--) {
        int c=(v>>i)&1;
        int nxt=trie[t][c][n];
        if(!nxt) {
            nxt=trie[t][c].size();
            trie[t][c][n]=nxt;
            mn[t].push_back(2e9);
            trie[t][0].push_back(0);
            trie[t][1].push_back(0);
        }
        mn[t][nxt]=min(mn[t][nxt], tmp);
        n=nxt;
    }
}

int search(int t, int v, int tmp) {
    int n=0;
    int ans=0;
    for(int i=31;i>=0;i--) {
        int c=(v>>i)&1;
        int nxt=trie[t][c^1][n];
        if(nxt&&mn[t][nxt]<=tmp) {
            ans|=1<<i;
        } else nxt=trie[t][c][n];
        n=nxt;
    }
    return ans;
}

void dfs1(int v) {
    sz[v]=1;
    for(auto u : chi[v]) {
        dfs1(u);
        sz[v]+=sz[u];
    }
}

void dfs2(int v) {
    int bst=0;
    for(auto u : chi[v]) {
        if(sz[u]>sz[bst]) bst=u;
    }
    if(!bst) {
        id[v]=v;
        mn[v].push_back(v);
        trie[v][0].push_back(0);
        trie[v][1].push_back(0);
    } else {
        dfs2(bst);
        id[v]=id[bst];
    }
    for(auto u : chi[v]) {
        if(u==bst) continue;
        dfs2(u);
        for(auto pr : vec[id[u]]) {
            insert(id[v], pr.second, pr.first);
            vec[id[v]].push_back(pr);
        }
        for(int i=0;i<2;i++) trie[id[u]][i].clear();
        vec[id[u]].clear();
    }
    vec[id[v]].push_back({v, val[v]});
    insert(id[v], val[v], v);
    for(auto pr : qs[v]) {
        int i=pr.first, vl=pr.second.first, t=pr.second.second;
        ans[i]=search(id[v], vl, t);
    }
}

int main() {
    memset(ans, 0xff, sizeof(ans));
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    val[1]=0;
    int q;
    cin >> q;
    for(int i=0;i<q;i++) {
        string op;
        cin >> op;
        if(op=="Add") {
            int x, y;
            cin >> x >> y;
            ++t;
            chi[x].push_back(t);
            val[t]=val[x]^y;
        } else {
            int a, b;
            cin >> a >> b;
            qs[b].push_back({i, {val[a], t}});
        }
    }
    sz[0]=0;
    dfs1(1);
    dfs2(1);
    for(int i=0;i<q;i++) {
        int a=ans[i];
        if(a>=0) cout << a << "\n";
    }
}

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