888G - Xor-MST - CodeForces Solution

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
 
class UnionFind {
private:
    vector<int> p, setSize;
    int numSets;
public:
    vector<vector<int>> adj;
 
    UnionFind(int N) {
        p.assign(N, 0);
        for (int i = 0; i < N; i++) {
            p[i] = i;
        }
        setSize.assign(N, 1);
        numSets = N;
        adj.resize(N);
        for (int i = 0; i < N; i++) {
            adj[i].push_back(i);
        }
    }
 
    int findSet(int i) {
        return (p[i] == i) ? i : (p[i] = findSet(p[i]));
    }
 
    bool isSameSet(int i, int j) {
        return findSet(i) == findSet(j);
    }
 
    int numDisjointSets() {
        return numSets;
    }
 
    int sizeOfSet(int i) {
        return setSize[findSet(i)];
    }
 
    void unionSet(int i, int j) {
        if (isSameSet(i, j)) return;
        int x = findSet(i), y = findSet(j);
        if (setSize[x] > setSize[y]) swap(x, y);
        p[x] = y;
        setSize[y] += setSize[x];
        numSets--;
        for (auto &x: adj[x]) {
            adj[y].push_back(x);
        }
        adj[x].clear();
    }
};

const int N = 2e5 + 9;
 
int t[N * 30][2], sz;
int el[N * 30], tot[N * 30];
void add(int x, int id) {
    int cur = 0;
    tot[cur]++;
    for (int i=30; i>=0; i--) {
        bool b = x&(1<<i);
        if (t[cur][b] == 0) t[cur][b] = ++sz;
        cur = t[cur][b];
        tot[cur]++;
    }
    el[cur] = id;
}
 
void del(int x, int id) {
    int cur = 0;
    tot[cur]--;
    for (int i=30; i>=0; i--) {
        bool b = x&(1<<i);
        cur = t[cur][b];
        tot[cur]--;
    }
    assert(el[cur] == id);
    el[cur] = 0;
}
 
int minxor(int x) {
    int cur = 0;
    for (int i=30; i>=0; i--) {
        bool b = x&(1<<i);
        if (t[cur][b] && tot[t[cur][b]] > 0)  cur = t[cur][b];
        else cur = t[cur][!b];
    }
    // assert(el[cur]);
    return el[cur];
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int n;
    cin >> n;
 
    vector<int> a(n);
    for (auto &x: a) cin >> x;
 
    sort(a.begin(), a.end());
    a.resize(unique(a.begin(), a.end()) - a.begin());
    n = a.size();
 
    UnionFind dsu(n);
    ll ans = 0;
 
    for (int i = 0; i < n; i++) {
        add(a[i], i);
    }
 
    int cntIterations = 0;
    while (dsu.numDisjointSets() > 1) {
        cntIterations++;
        assert(cntIterations <= 25);
        vector<pair<int, int>> toMerge;
        
        for (int i = 0; i < n; i++) {
            auto &comp = dsu.adj[i];
            if (dsu.findSet(i) != i || (int) comp.size() == 0) continue;
            for (auto &x: comp) {
                del(a[x], x);
            }
            
            int from = -1, to = -1;
            for (auto &i: comp) {
                int cur = minxor(a[i]);
                if (from == -1 || ((a[i] ^ a[cur]) < (a[from] ^ a[to]))) {
                    from = i;
                    to = cur;
                }
            }
 
            assert(from != -1 && to != -1);
            toMerge.push_back({from, to});
 
            for (auto &x: comp) {
                add(a[x], x);
            }
        }
 
        assert(!toMerge.empty());
        for (auto &[from, to]: toMerge) {
            if (!dsu.isSameSet(from, to)) {
                dsu.unionSet(from, to);
                ans += a[from] ^ a[to];
            }
        }
    }
 
    cout << ans;
}