s4v9m7 - Online C++0x Compiler & Debugging Tool

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

const int limN = 2e5 + 5;
const int MAX_NODES = 12500005;
const long long INF = 4e18;

int child[MAX_NODES][2];
int c1[MAX_NODES], c2[MAX_NODES];
int id1[MAX_NODES], id2[MAX_NODES];
int nnode = 0;

inline int new_node() {
    int u = ++nnode;
    child[u][0] = child[u][1] = 0;
    c1[u] = c2[u] = id1[u] = id2[u] = 0;
    return u;
}

inline void add(int u, int c, int id) {
    if (!c1[u]) {
        c1[u] = c;
        id1[u] = id;
    }
    else if (c1[u] != c && !c2[u]) {
        c2[u] = c;
        id2[u] = id;
    }
}

inline bool check(int u, int c) {
    if (!u) return false;
    if (c1[u] != c) return true;
    return c2[u] != 0;
}

inline int other(int u, int c) {
    if (c1[u] != c) return id1[u];
    return id2[u];
}

inline void insert(int root, long long val, int c, int id) {
    int u = root;
    add(u, c, id);
    for (int i = 30; i >= 0; --i) {
        int bit = (val >> i) & 1;
        if (!child[u][bit])
            child[u][bit] = new_node();

        u = child[u][bit];
        add(u, c, id);
    }
}

inline int get(int root, long long val, int c) {
    int u = root;
    for (int i = 30; i >= 0; --i) {
        int bit = (val >> i) & 1;

        int x = child[u][bit];
        if (x && check(x, c)) u = x;
        else u = child[u][!bit];
    }
    return other(u, c);
}

struct DSU {
    vector<int> lab;
    DSU(int n) : lab(n + 1, -1) {}

    int find(int u) {
        return lab[u] < 0 ? u : lab[u] = find(lab[u]);
    }

    bool unite(int u, int v) {
        u = find(u); v = find(v);
        if (u == v) return false;
        if (lab[u] > lab[v]) swap(u, v);
        lab[u] += lab[v]; lab[v] = u;
        return true;
    }
};

struct Edge {
    long long w;
    int u, v;
};

int n, comp[limN];
long long a[limN], b[limN], k;
Edge best[limN];

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        b[i] = a[i] + k;
    }

    DSU dsu(n);
    long long ans = 0;
    int numcomp = n;

    vector<Edge> tmp;
    tmp.reserve(n);

    while (numcomp > 1) {
        nnode = 0;
        int A = new_node(), B = new_node();

        for (int i = 1; i <= n; ++i) {
            comp[i] = dsu.find(i);
            insert(A, a[i], comp[i], i);
            insert(B, b[i], comp[i], i);
            best[i] = {INF, -1, -1};
        }

        for (int i = 1; i <= n; ++i) {
            int c = comp[i];

            int v1 = get(B, a[i], c);
            long long w1 = a[i] ^ b[v1];
            if (w1 < best[c].w)
                best[c] = {w1, i, v1};

            int v2 = get(A, b[i], c);
            long long w2 = b[i] ^ a[v2];
            if (w2 < best[c].w)
                best[c] = {w2, i, v2};
        }

        tmp.clear();
        for (int i = 1; i <= n; ++i) {
            if (comp[i] == i && best[i].w != INF) {
                tmp.push_back(best[i]);
            }
        }

        bool ok = false;
        for (const Edge &it : tmp) {
            if (dsu.unite(it.u, it.v)) {
                ans += it.w;
                --numcomp;
                ok = true;
            }
        }

        if (!ok) break;
    }

    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    solve();
    return 0;
}