Xor-MST (Codeforces 888G)
Tags: Others, bitmasks

You are given a complete undirected graph with n vertices. A number ai is assigned to each vertex, and the weight of an edge between vertices i and j is equal to ai xor aj.Calculate the weight of the minimum spanning tree in this graph.

Input: The first line contains n (1 ≤ n ≤ 200000) — the number of vertices in the graph.The second line contains n integers a1, a2, ..., an (0 ≤ ai < 230) — the numbers assigned to the vertices.

Output: Print one number — the weight of the minimum spanning tree in the graph.


Sample Inputs:
5
1 2 3 4 5

4
1 2 3 4

Sample Outputs:
8

8

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def insert(x, la):
    j = 0
    for i in p:
        if x & i:
            if not G1[j]:
                la += 1
                G1[j] = la
                j = la
            else:
                j = G1[j]
        elif not G0[j]:
            la += 1
            G0[j] = la
            j = la
        else:
            j = G0[j]
        cnt[j] += 1
    return la

def xor_min(x, s):
    (j, ans) = (s, 0)
    for i in range(30 - len(st), -1, -1):
        if x & pow2[i]:
            if G1[j]:
                j = G1[j]
            else:
                ans ^= pow2[i]
                j = G0[j]
        elif G0[j]:
            j = G0[j]
        else:
            ans ^= pow2[i]
            j = G1[j]
    return ans
n = int(input())
a = list(map(int, input().split()))
a = list(set(a))
a.sort()
pow2 = [1]
l = 30
for _ in range(l):
    pow2.append(2 * pow2[-1])
p = pow2[::-1]
n = len(a)
(G0, G1, cnt, la) = ([0] * 5000000, [0] * 5000000, [0] * 5000000, 0)
for i in a:
    la = insert(i, la)
h = l
l0 = [-1] * (la + 1)
l0[0] = 0
st = [0]
ans = 0
while st:
    i = st[-1]
    (j, k) = (G0[i], G1[i])
    if l0[j] == -1 and l0[k] == -1 and min(cnt[j], cnt[k]):
        l = l0[i]
        m = l + cnt[j]
        r = m + cnt[k]
        ans0 = pow2[30]
        if (m - l) * (r - m) <= 5000:
            for u in range(l, m):
                au = a[u]
                for v in range(m, r):
                    ans0 = min(ans0, au ^ a[v])
        elif m - l <= r - m:
            for u in range(l, m):
                ans0 = min(ans0, xor_min(a[u], k))
        else:
            for u in range(m, r):
                ans0 = min(ans0, xor_min(a[u], j))
        ans0 |= pow2[h]
        ans += ans0
    if l0[j] == -1:
        if cnt[j] > 1:
            st.append(j)
            h -= 1
        l0[j] = l0[i]
    elif l0[k] == -1:
        if cnt[k] > 1:
            st.append(k)
            h -= 1
        l0[k] = l0[i] + cnt[j]
    else:
        st.pop()
        h += 1
print(ans)

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def binary_trie():
    (G0, G1, color) = ([-1], [-1], [0])
    return (G0, G1, color)

def insert(x, c):
    j = 0
    for i in range(l, -1, -1):
        color[j] = c
        if x & pow2[i]:
            if not G1[j] ^ -1:
                G0.append(-1)
                G1.append(-1)
                color.append(0)
                G1[j] = len(color) - 1
            j = G1[j]
        else:
            if not G0[j] ^ -1:
                G0.append(-1)
                G1.append(-1)
                color.append(0)
                G0[j] = len(color) - 1
            j = G0[j]
    color[j] = c
    return

def xor_min(x, c):
    j = 0
    ans = 0
    for i in range(l, -1, -1):
        if not x & pow2[i]:
            if G0[j] ^ -1 and (not color[G0[j]] ^ c):
                j = G0[j]
            else:
                ans += pow2[i]
                j = G1[j]
        elif G1[j] ^ -1 and (not color[G1[j]] ^ c):
            j = G1[j]
        else:
            ans += pow2[i]
            j = G0[j]
    return ans
n = int(input())
a = list(map(int, input().split()))
s = set(a)
a = list(s)
a.sort()
pow2 = [1]
for _ in range(30):
    pow2.append(2 * pow2[-1])
n = len(s)
st = [(0, n, 30)]
ans = 0
l = 30
(G0, G1, color) = binary_trie()
c = 0
while st:
    (u, v, l0) = st.pop()
    c += 1
    p2 = pow2[l0]
    if p2 & a[u] == p2 & a[v - 1]:
        if u ^ v and l0 > 0:
            st.append((u, v, l0 - 1))
        continue
    m = u
    while not a[m] & p2:
        m += 1
    (x, y) = ([u, m], [m, v])
    if m - u > v - m:
        (x, y) = (y, x)
    ans0 = pow2[l0 + 1]
    if (m - u) * (v - m) < 500:
        for i in range(x[0], x[1]):
            ai = a[i]
            for j in range(y[0], y[1]):
                ans0 = min(ans0, ai ^ a[j])
    else:
        for i in range(x[0], x[1]):
            insert(a[i], c)
        for i in range(y[0], y[1]):
            ans0 = min(ans0, xor_min(a[i], c))
    ans += ans0
    if u ^ m and l0 > 0:
        st.append((u, m, l0 - 1))
    if m ^ v and l0 > 0:
        st.append((m, v, l0 - 1))
print(ans)

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def insert(x, la):
    j = 0
    for i in p:
        if x & i:
            if not G[j] >> 25:
                la += 1
                G[j] ^= la << 25
                j = la
            else:
                j = G[j] >> 25
        elif not G[j] & 33554431:
            la += 1
            G[j] ^= la
            j = la
        else:
            j = G[j] & 33554431
        cnt[j] += 1
    return la

def xor_min(x, s):
    (j, ans) = (s, 0)
    for i in range(30 - len(st), -1, -1):
        if x & pow2[i]:
            if G[j] >> 25:
                j = G[j] >> 25
            else:
                ans ^= pow2[i]
                j = G[j] & 33554431
        elif G[j] & 33554431:
            j = G[j] & 33554431
        else:
            ans ^= pow2[i]
            j = G[j] >> 25
    return ans
n = int(input())
a = list(map(int, input().split()))
a = list(set(a))
a.sort()
pow2 = [1]
l = 30
for _ in range(l):
    pow2.append(2 * pow2[-1])
p = pow2[::-1]
n = len(a)
(G, cnt, la) = ([0] * 5000000, [0] * 5000000, 0)
for i in a:
    la = insert(i, la)
h = l
l0 = [-1] * (la + 1)
l0[0] = 0
st = [0]
ans = 0
while st:
    i = st[-1]
    (j, k) = (G[i] & 33554431, G[i] >> 25)
    if l0[j] == -1 and l0[k] == -1 and min(cnt[j], cnt[k]):
        l = l0[i]
        m = l + cnt[j]
        r = m + cnt[k]
        ans0 = pow2[30]
        if (m - l) * (r - m) <= 5000:
            for u in range(l, m):
                au = a[u]
                for v in range(m, r):
                    ans0 = min(ans0, au ^ a[v])
        elif m - l <= r - m:
            for u in range(l, m):
                ans0 = min(ans0, xor_min(a[u], k))
        else:
            for u in range(m, r):
                ans0 = min(ans0, xor_min(a[u], j))
        ans0 |= pow2[h]
        ans += ans0
    if l0[j] == -1:
        if cnt[j] > 1:
            st.append(j)
            h -= 1
        l0[j] = l0[i]
    elif l0[k] == -1:
        if cnt[k] > 1:
            st.append(k)
            h -= 1
        l0[k] = l0[i] + cnt[j]
    else:
        st.pop()
        h += 1
print(ans)