记录编号	597071	评测结果	AAAAAAAAAA
题目名称	Xor-MST	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	10.398 s
提交时间	2024-11-21 14:12:11	内存使用	65.61 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define fi first
#define in inline
#define se second
#define mp make_pair
#define pb push_back
const int N = 2e5+10;

ll read(){
	ll x = 0,f = 1;char c = getchar();
	for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
	for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
	return x * f;
}

int n;
int a[N];

struct Trie{
	int son[N*40][2],siz[N*40],id[N*40],cnt = 1;
	void insert(int x,int i){
		int p = 1;
		for(int i = 31;i >= 0;i--){
			int bit = x >> i & 1;
			if(!son[p][bit])son[p][bit] = ++cnt;
			p = son[p][bit];
			siz[p]++;
		}
		id[p] = i;
	}
	void del(int x){
		int p = 1;
		for(int i = 31;i >= 0;i--){
			int bit = x >> i & 1;
			p = son[p][bit];
			siz[p]--;
		}
	}
	pii ask(int x){
		int p = 1;ll s = 0;
		for(int i = 31;i >= 0;i--){
			int bit = x >> i & 1;
			if(son[p][bit] && siz[son[p][bit]])p = son[p][bit];
			else p = son[p][bit ^ 1],s += (1ll << i);
		}
		return {s,id[p]};
	}
}t;

int cnt;
struct DSU{
	int fa[N];
	void clear(){for(int i = 1;i <= n;i++)fa[i] = i;}
	int find(int x){return x == fa[x] ? x : fa[x] = find(fa[x]);}
	void merge(int x,int y){
		x = find(x),y = find(y);
		if(x == y)return;
		fa[x] = y,cnt--;
	}
}U;

ll sum = 0;
vector<int>c[N];
int main(){
	n = read();
	U.clear();
	cnt = n;
	for(int i = 1;i <= n;i++)a[i] = read();
	sort(a+1,a+1+n);
	for(int i = 1;i <= n;i++)t.insert(a[i],i);
	while(1){
		if(cnt == 1)break;
		for(int i = 1;i <= n;i++)c[i].clear();
		for(int i = 1;i <= n;i++)c[U.find(i)].pb(i);
		for(int i = 1;i <= n;i++)
			if(i == U.fa[i]){
				for(int x : c[i])
					t.del(a[x]);
				pii ans = {1e10,0};
				for(int x : c[i]){
					pii s = t.ask(a[x]);
					if(s.fi < ans.fi)ans = s;
				}
				if(U.find(i) != U.find(ans.se))sum += ans.fi;
				U.merge(i,ans.se);
				for(int x : c[i])t.insert(a[x],x);
			}
	}
	printf("%lld\n",sum);

	return 0;

}