Submission #1182399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182399		tin.le22	Klasika (COCI20_klasika)	C++20	0 / 110	5094 ms	77856 KiB

klasika

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
const int MX = 200005;
const int MK = 31;
const int INF = 1e9;
 
int T[MX * MK * 3][2], ptr;
int cnt[MX * MK * 3], mn[MX * MK * 3];
 
class Binary_Trie {
public:
    void insert(ll num, int v = 1, int root = 0, int t = 0) {
        int curr = root;
        for (int i = MK - 1; i >= 0; i--) {
            int bits = (num >> i) & 1;
            if (!T[curr][bits]) {
                T[curr][bits] = ++ptr;
                cnt[ptr] = 0;
                mn[ptr] = INF;
            }
            curr = T[curr][bits];
            cnt[curr] += v;
            mn[curr] = min(mn[curr], t);
        }
    }
    
    ll max_xor(ll num, int root = 0, int t = INF) {
        ll res = 0;
        int curr = root;
        for (int i = MK - 1; i >= 0; i--) {
            int bits = (num >> i) & 1;
            int nxt = T[curr][!bits];
            if (nxt && cnt[nxt] && mn[nxt] <= t) {
                curr = T[curr][!bits];
                res |= (1LL << i);
            } else {
                curr = T[curr][bits];
            }
            if (!curr) break;
        }
        return res;
    }
};
 
void reset() {
    for (int i = 0; i <= ptr; i++) {
        T[i][0] = T[i][1] = 0;
        cnt[i] = 0;
        mn[i] = 0;
    }
    ptr = 0;
}
 
Binary_Trie Tree;
 
#define all(x) (x).begin(), (x).end()
 
vector<array<int,3>> graph[MX];
vector<vector<pair<int,int>>> Q(MX);
 
int n = 1;
 
vector<int> a;
vector<int> tin, tout;
int timer = 1;
 
void dfs(int node, int par) {
    tin[node] = timer++;
    for(auto &edge : graph[node]) {
        int v = edge[0], w = edge[1];
        if(v == par) continue;
        a[v] = a[node] ^ w;
        dfs(v, node);
    }
    tout[node] = timer - 1;
}
 
vector<int> ans;
 
pair<int, vector<pair<int,int>>> dsu_dfs(int node, int par, int t_val) {
    vector<pair<int,int>> s;
    s.push_back({a[node], t_val});
    int trie_root = 0;
    Tree.insert(a[node], 1, trie_root, t_val);
    for(auto &edge : graph[node]) {
        int v = edge[0], w = edge[1], nt = edge[2];
        if(v == par) continue;
        a[v] = a[node] ^ w;
        auto child = dsu_dfs(v, node, nt);
        if(child.second.size() > s.size()) {
            swap(s, child.second);
            swap(trie_root, child.first);
        }
        s.insert(s.end(), all(child.second));
        for(auto &p : child.second) {
            Tree.insert(p.first, 1, trie_root, p.second);
        }
    }
    for(auto &p : Q[node]) {
        int u = p.first, qid = p.second;
        ans[qid] = Tree.max_xor(a[u], trie_root, qid);
    }
    return {trie_root, s};
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    reset();
    int q; cin >> q;
    vector<array<int,4>> queries(q);
    for (int i = 1; i <= q; i++){
        string op; cin >> op;
        if(op == "Add"){
            int u, x; cin >> u >> x;
            int v = ++n;
            graph[u].push_back({v, x, i});
        } else {
            int u, x; cin >> u >> x;
            Q[x].push_back({u, i});
        }
    }
    a.resize(n+1, 0);
    tin.resize(n+1, 0);
    tout.resize(n+1, 0);
    ans.resize(q+1, -1);
    dfs(1, 0);
    dsu_dfs(1, 0, 1);
    for (int i = 1; i <= q; i++){
        if(ans[i] != -1) cout << ans[i] << "\n";
    }
    return 0;
}

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