Submission #1174865

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174865		_wesstiov_	Klasika (COCI20_klasika)	C++17	110 / 110	669 ms	375088 KiB

klasika

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

#define ll long long
#define fi first
#define sc second

const int MXN = 2e5;
const int INF = 1e9;
int q , n = 1;
vector<int> adj[MXN + 5];
int dist[MXN + 5];
struct Query{
    int d , sz , i;
};
vector<Query> query[MXN + 5];

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

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

    Trie(){
        trie = vector<Node>(1);
    }

    void addNum(int u){
        int v = 0;

        for (int i = 30 ; i >= 0; i--){
            bool bit = (dist[u] >> i) & 1;
            if (trie[v].nxt[bit] == -1){
                trie.push_back(Node());
                trie[v].nxt[bit] = trie.size() - 1;
            }

            v = trie[v].nxt[bit];
            trie[v].mark = min(trie[v].mark , u);
        }
    }

    int getMaxXor(int d, int sz){
        int v = 0 , ans = 0;

        for (int i = 30; i >= 0 ;i--){
            bool bit = (d >> i) & 1;
            int nxt_v0 = trie[v].nxt[bit] , nxt_v1 = trie[v].nxt[bit ^ 1];

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

        return ans;
    }
};

int ANS[MXN + 1];
set<int> s[MXN + 1];
Trie ver[MXN + 1];

void dfs(int u,int par){
    s[u].insert(u);
    ver[u].addNum(u);

    for (auto v : adj[u]){
        if (v == par) continue;

        dfs(v , u);
        if (s[u].size() < s[v].size()) {
            swap(s[u] , s[v]);
            swap(ver[u] , ver[v]);
        }
        for (auto x : s[v]) {
            s[u].insert(x);
            ver[u].addNum(x);
        }
    }

    for (auto [d , sz , i] : query[u]){
        //cout << d <<' ' << sz << ' ' << i <<'\n';
        ANS[i] = ver[u].getMaxXor(d , sz);
    }
}

signed main(){
    cin.tie(0)->ios_base::sync_with_stdio(0);
//    freopen(".INP" ,"r" , stdin);
//    freopen(".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;
            n++;
            dist[n] = (dist[x] ^ y);
            adj[x].push_back(n);
            adj[n].push_back(x);
        }else {
            int a , b; cin >> a >> b;
            query[b].push_back({dist[a] , n , i});
        }
    }
    memset(ANS , -1 , sizeof ANS);
    dfs(1 , -1);

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

/*
6
Add 1 5
Add 2 7
Add 1 4
Add 4 3
Query 1 1
Query 2 4

4
Add 1 5
Query 1 1
Add 1 7
Query 1 1

10
Add 1 4
Add 1 9
Add 1 10
Add 2 2
Add 3 3
Add 4 4
Query 4 2
Query 1 3
Add 6 7
Query 1 3
*/

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