Submission #1276024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276024		papaulo	Klasika (COCI20_klasika)	C++20	33 / 110	1743 ms	589824 KiB

klasika

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

#define MAXQ 200200
int id[MAXQ];
vector<int> chi[MAXQ];
int t=1;
int val[MAXQ];
unordered_map<int, int> mp[MAXQ][32];
vector<pair<int, pair<int, int>>> qs[MAXQ];
int ans[MAXQ];
int sz[MAXQ];

int search(int t, int v, int tmp) {
    int n=0;
    int ans=0;
    for(int i=31;i>=0;i--) {
        int m=1<<i;
        int c=v&m;
        int nxt=n|(c^m);
        auto p = mp[t][i].find(nxt);
        if(p!=mp[t][i].end()&&p->second<=tmp) {
            ans|=1<<i;
        } else nxt=n|c;
        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;
    } else {
        dfs2(bst);
        id[v]=id[bst];
    }
    for(auto u : chi[v]) {
        if(u==bst) continue;
        dfs2(u);
        for(int i=0;i<32;i++) {
            for(auto pr : mp[id[u]][i]) {
                auto p = mp[id[v]][i].find(pr.first);
                if(p==mp[id[v]][i].end()) mp[id[v]][i].insert(pr);
                else p->second=min(p->second, pr.second);
            }
            mp[id[u]][i].clear();
        }
    }
    int n=0;
    for(int i=31;i>=0;i--) {
        n|=(val[v]&(1<<i));
        mp[id[v]][i][n]=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: 0 / 33
• Subtask 4: 0 / 44