Submission #1270739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270739		_wesstiov_	Klasika (COCI20_klasika)	C++17	110 / 110	581 ms	339828 KiB

klasika

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

#define ll long long
const int MXN = 2e5;
const int INF = 1e9;
int n = 1, q;
vector<int> adj[MXN + 5];
int dist[MXN + 5];

struct Coup{
    int a ,sz , i;

    Coup (int a,int sz,int i) : a(a) , sz(sz)  , i(i){}
};

vector<Coup> query[MXN + 5];

struct Trie{
    struct Node{
        int nxt[2];
        int mark = INF;

        Node(){
            memset(nxt , -1 ,sizeof nxt);
        }
    };
    vector<Node> trie = vector<Node>(1);

    void addNum(int x ,int t){
        int v = 0;
        for (int i = 30; i >= 0; i--){
            bool b = (x >> i & 1);
            if (trie[v].nxt[b] == -1){
                trie.push_back(Node());
                trie[v].nxt[b] = trie.size() - 1;
            }
             v = trie[v].nxt[b];
             trie[v].mark = min(trie[v].mark , t);
        }

        return;
    }

    int getMax(int x,int t){
        int v = 0 , ans = 0;
        for (int i = 30; i >= 0; i--){
            bool b = (x >> i & 1);
            int nxt_v0 = trie[v].nxt[b] , nxt_v1 = trie[v].nxt[b ^ 1];

            if (nxt_v1 != -1 and trie[nxt_v1].mark <= t){
                v = nxt_v1;
                ans |= (1 << i);
            }else v = nxt_v0;

            if (v == -1 or trie[v].mark > t) return 0;
        }

        return ans;
    }
};
vector<int> lst[MXN + 5];
Trie vex[MXN + 5];

int ANS[MXN + 5];

void dfs(int u,int par){
    lst[u].emplace_back(u);
    vex[u].addNum(dist[u] , u);
    for (auto v : adj[u]){
        if (v == par) continue;
        dfs(v , u);

        if (lst[u].size() < lst[v].size()) {
            swap(lst[u] , lst[v]);
            swap(vex[u] , vex[v]);
        }
        for (auto p : lst[v]) {
            lst[u].emplace_back(p);
            vex[u].addNum(dist[p] , p);
        }
    }

    for (auto [a , sz , i] : query[u]){
        ANS[i] = vex[u].getMax(a , sz);
    }
}

signed main(){
    cin.tie(0)->ios_base::sync_with_stdio(0);
//    freopen("SPEED.INP" , "r" , stdin);
//    freopen("SPEED.OUT" , "w" , stdout);

    cin >> q;
    for (int i = 1; i <= q;i++){
        string type; cin >> type;

        if (type == "Add"){
            int x , y; cin >> x >> y;
            adj[x].emplace_back(++n);
            adj[n].emplace_back(x);
            dist[n] = dist[x] ^ y;
        }else{
            int a, b; cin >> a >> b;
            query[b].emplace_back(dist[a] , n , i);
        }
    }
    memset(ANS , -1 , sizeof ANS);
    dfs(1 , 1);

    for (int i = 1; i <= q ;i++){
        if (ANS[i] == -1) continue;
        cout << ANS[i] <<'\n';
    }
}

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