VNEMPIRE - Đế chế

Tác giả: khuc_tuan

Ngôn ngữ: C++

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define Rep(i,n) for(int i=0;i<(n);++i)
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Ford(i,a,b) for(int i=(a);i>=(b);--i)
#define fi first
#define se second
#define pb push_back
#define MP make_pair

int x[100010],y[100010],z[100010];
int n, ne;
pair<int,int> a[100010],b[100010],c[100010];
pair<int,pair<int,int> > e[300010];
int f[100010];

int getroot(int i){
	if(f[i]<0)return i;else return getroot(f[i]);
}

int main() {
	scanf("%d",&n);
	Rep(i,n){
		scanf("%d%d%d",x+i,y+i,z+i);
		a[i]=make_pair(x[i],i);
		b[i]=make_pair(y[i],i);
		c[i]=make_pair(z[i],i);
	}
	sort(a,a+n);
	sort(b,b+n);
	sort(c,c+n);
	Rep(i,n-1)e[ne++].second=make_pair(a[i].second,a[i+1].second);
	Rep(i,n-1)e[ne++].second=make_pair(b[i].second,b[i+1].second);
	Rep(i,n-1)e[ne++].second=make_pair(c[i].second,c[i+1].second);
	Rep(i,ne)e[i].first=min(min(abs(x[e[i].se.fi]-x[e[i].se.se]),abs(y[e[i].se.fi]-y[e[i].se.se])),abs(z[e[i].se.fi]-z[e[i].se.se]));
	sort(e,e+ne);
	long long res=0;
	memset(f,-1,sizeof(f));
	Rep(i,ne){
		int u=getroot(e[i].se.fi);
		int v=getroot(e[i].se.se);
		if(u!=v){
			res+=e[i].fi;
			if(f[u]<f[v])f[u]+=f[v],f[v]=u;
			else f[v]+=f[u],f[u]=v;
		}
	}
	cout<<res<<endl;
	return 0;	
}

Download