Code:
// luogu-judger-enable-o2 #include<bits/stdc++.h> #define setIO(s) freopen(s".in","r",stdin) #define maxn 4100000 #define ll long long using namespace std; int u[maxn],v[maxn],p[3000],A[maxn]; ll arr[3000],val[maxn]; int n,edges; int find(int x) { return p[x]==x?x:p[x]=find(p[x]); } bool merge(int a,int b) { int x=find(a),y=find(b); if(x==y) return false; p[x]=y; return true; } bool cmp(const int i,const int j) { return val[i]>val[j]; } int main() { // setIO("input"); scanf("%d",&n); for(int i=0;i<3000;++i) p[i]=i; for(int i=1;i<=n;++i) scanf("%lld",&arr[i]); for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) { if(i==j) continue; A[++edges]=edges, u[edges]=i,v[edges]=j, val[edges]=arr[i]^arr[j]; } sort(A+1,A+1+edges,cmp); ll sum=0; int cc=0; for(int i=1;i<=edges;++i) { int e=A[i]; int a=u[e],b=v[e]; if(merge(a,b)) sum+=val[e],++cc; if(cc==n-1) break; } printf("%lld\n",sum); return 0; }