Submission #5542578

---

Source Code Expand

// È¥°É£¡Æ¤¿¨Çð! °ÑAC´ø»ØÀ´£¡
//      ¤Ø¡¡¡¡¡¡¡¡¡¡£¯|
// ¡¡¡¡/£Ü7¡¡¡¡¡¡ ¡Ï£ß/
// ¡¡ /¡¡©¦¡¡¡¡ £¯¡¡£¯								AC		AC		AC		AC
//    ©¦¡¡Z £ß,£¼¡¡£¯¡¡¡¡ /`©c						AC		AC		AC		AC
//    ©¦¡¡¡¡¡¡¡¡¡¡©c¡¡¡¡ /¡¡¡¡¡µ					AC		AC		AC		AC
// ¡¡Y¡¡¡¡¡¡¡¡¡¡`¡¡ /¡¡¡¡/  /						AC		AC		AC		AC
// ¡¡Øé¡ñ¡¡.¡¡¡ñ¡¡¡¡¡´¡¡/¡¡/						AC		AC		AC		AC
// ¡¡()¡¡ ¤Ø¡¡¡¡¡¡¡¡|¡¡£Ü¡´							AC		AC		AC		AC
// ¡¡¡¡>- ._¡¡ ¥£¡¡ ©¦ £¯£¯							AC		AC		AC		AC
// ¡¡ / ¤Ø¡¡¡¡ /¡¡/£¼| £Ü£Ü							AC		AC		AC		AC
// ¡¡ ©c_/¡¡¡¡(_£¯¡¡ ©¦£¯£¯							AC		AC		AC		AC
// ¡¡¡¡ 7¡¡¡¡¡¡¡¡¡¡¡¡¡¡|£¯							AC		AC		AC		AC
// ¡¡¡¡ £¾¨Dr£þ£þ`-¨D£ß/							AC		AC		AC		AC
//**************************************Accepted*****************************************//

#include<bits/stdc++.h>

#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define Unique(x) x.erase(unique(all(x)),x.end);

#define CIN_FILE "input.txt"
#define COUT_FILE "output.txt"

using namespace std;

const int dx[]={-1,0,1,0};
const int dy[]={0,-1,0,1};

typedef long long ll;

int n,x[100010],y[100010],pa[100010];
pair<int,int> sx[100010],sy[100010];
int ans;

inline bool cmp(pair<int,int> x,pair<int,int> y){return x.first<y.first;}

inline int fnd(int x){return (x==pa[x] ? x : fnd(pa[x]));}

int Onion(int x,int y)
{
	x=fnd(x),y=fnd(y);
	
	if(x==y)return 0;
	
	pa[x]=y;
	return 1;
}

set<pair<int,pair<int,int> > > st;

int main(int argc, char const *argv[])
{
	ios::sync_with_stdio(false);
	
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>x[i]>>y[i];
		pa[i]=i;
		sx[i]=mp(x[i],i),sy[i]=mp(y[i],i);
	}
	
	sort(sx,sx+n,cmp);
	sort(sy,sy+n,cmp);
	
	for(int i=0;i<n-1;i++)
	{
		st.insert(mp(min((abs(x[sx[i].second]-x[sx[i+1].second])),(abs(y[sx[i].second]-y[sx[i+1].second]))),mp(sx[i].second,sx[i+1].second)));
		st.insert(mp(min((abs(x[sy[i].second]-x[sy[i+1].second])),(abs(y[sy[i].second]-y[sy[i+1].second]))),mp(sy[i].second,sy[i+1].second)));
	}
	
	while(!st.empty())
	{
		pair<int,pair<int,int> > cur=*(st.begin());
		st.erase(cur);
		
		int u=cur.second.first,v=cur.second.second;
		
		ans+=(Onion(u,v)*(min((abs(x[u]-x[v])),(abs(y[u]-y[v])))));
	}
	
	cout<<ans;
	
	//printf("Time used = %.6f",(double)(clock())/CLOCKS_PER_SEC);
	return 0;
}

Submission Info

Judge Result