Submission #11581211
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define DB double
#define ST string
#define BS bitset
#define VE vector
#define VL vector<LL>
#define VP vector<pair<LL,LL>>
#define VVL vector<vector<LL>>
#define PQ priority_queue<LL>
#define PQS priority_queue<LL, vector<LL>, greater<LL>>
#define PB push_back
#define POB pop_back
#define PF push_front
#define POF pop_front
#define MP make_pair
#define TS to_string
#define TU to_ullong
#define FOR(i,a,n) for(i=a;i<n;i++)
#define rep(i,n) FOR(i,0,n)
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define SORT(a) sort(ALL(a))
#define REV(a) reverse(ALL(a))
#define UB(a,n) *upper_bound(ALL(a),n)
#define LB(a,n) *lower_bound(ALL(a),n)
#define INF 1145141919810364364
#define PI 3.14159265358979
//#define MOD 1000000007
#define MOD 998244353
#define ERR 0.00000000000001
#define NUM 200010
void Yn(LL a){if(a)printf("Yes\n");else printf("No\n");}
void YN(LL a){if(a)printf("YES\n");else printf("NO\n");}
LL pwmn(LL a,LL n){LL ans=1;while(ans<a)ans*=n;return ans;}
LL GCD(LL a,LL b){LL c=1,tmp=max(a,b);b=min(a,b);a=tmp;while(c!=0){c=a%b;a=b;b=c;}return a;}
LL LCM(LL a,LL b){return a*b/GCD(a,b);}
LL mod(LL a,LL m){if(a<0)return a%m+m;else return a%m;}
LL DIV(LL a,LL d){LL m=MOD,x=1,y=0,k;while(m){k=d/m;d-=k*m;swap(m,d);x-=k*y;swap(x,y);}return mod(a*mod(x,MOD),MOD);}
LL FAC(LL a){LL i,ans=1;FOR(i,1,a+1){ans*=i;if(MOD>0&&ans>MOD)ans%=MOD;}return ans;}
LL POW(LL a,LL n){LL ans=1;while(n>0){if(n&1)ans=ans*a%MOD;a=a*a%MOD;n>>=1;}return ans;}
LL fact[NUM],finv[NUM],inv[NUM];
void comi(){LL i;fact[0]=fact[1]=1;finv[0]=finv[1]=1;inv[1]=1;FOR(i,2,NUM){fact[i]=fact[i-1]*i%MOD;inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;finv[i]=finv[i-1]*inv[i]%MOD;}}
LL com(LL n,LL k){if(n<k||n<0||k<0)return 0;return fact[n]*(finv[k]*finv[n-k]%MOD)%MOD;}
bool cmps(pair<LL,LL> a,pair<LL,LL> b){if(a.second!=b.second)return a.second<b.second;return a.first<b.first;}
struct UF{
private:
VL par;
public:
UF(LL n){par.resize(n,-1);}
LL root(LL x){if(par[x]<0)return x;else return par[x]=root(par[x]);}
LL size(LL x){return -par[root(x)];}
bool same(LL x,LL y){return root(x)==root(y);}
void unite(LL x,LL y){x=root(x);y=root(y);if(x!=y){if(size(x)<size(y))swap(x,y);par[x]+=par[y];par[y]=x;}}
};
typedef struct{LL s,e,c,n;}Edge;
bool cmpc(Edge a,Edge b){return a.c<b.c;}
struct Kruscal{
private:UF *uf;VE<Edge> ed;
public:
VE<Edge> edge;
Kruscal(LL N){uf=new UF(N);}
void add(LL s,LL e,LL c,LL n=0){Edge f;f.s=s,f.e=e,f.c=c,f.n=n;ed.PB(f);}
void run(){sort(ALL(ed),cmpc);for(Edge a:ed){if(uf->same(a.s,a.e))continue;else{edge.PB(a);uf->unite(a.s,a.e);}}}
};
typedef struct{LL x,y,n;}Node;
bool cmpx(Node a,Node b){return a.x<b.x;}
bool cmpy(Node a,Node b){return a.y<b.y;}
int main(){
LL i,N,ans=0;
cin>>N;
VE<Node> v(N);
Kruscal k(2*N-2);
rep(i,N){
cin>>v[i].x>>v[i].y;
v[i].n=i;
}
sort(ALL(v),cmpx);
rep(i,N-1)k.add(v[i].n,v[i+1].n,v[i+1].x-v[i].x);
sort(ALL(v),cmpy);
rep(i,N-1)k.add(v[i].n,v[i+1].n,v[i+1].y-v[i].y);
k.run();
for(Edge a:k.edge)ans+=a.c;
cout<<ans<<endl;
}
Submission Info
Submission Time |
|
Task |
D - Built? |
User |
Hexazine |
Language |
C++14 (GCC 5.4.1) |
Score |
500 |
Code Size |
3193 Byte |
Status |
AC |
Exec Time |
149 ms |
Memory |
19816 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
500 / 500 |
Status |
|
|
Set Name |
Test Cases |
Sample |
s1.txt, s2.txt |
All |
01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, s1.txt, s2.txt |
Case Name |
Status |
Exec Time |
Memory |
01.txt |
AC |
149 ms |
18920 KB |
02.txt |
AC |
149 ms |
18664 KB |
03.txt |
AC |
148 ms |
18152 KB |
04.txt |
AC |
148 ms |
17768 KB |
05.txt |
AC |
149 ms |
18792 KB |
06.txt |
AC |
149 ms |
18408 KB |
07.txt |
AC |
148 ms |
18152 KB |
08.txt |
AC |
149 ms |
18408 KB |
09.txt |
AC |
144 ms |
18152 KB |
10.txt |
AC |
145 ms |
19432 KB |
11.txt |
AC |
145 ms |
18792 KB |
12.txt |
AC |
145 ms |
18664 KB |
13.txt |
AC |
111 ms |
18408 KB |
14.txt |
AC |
112 ms |
19432 KB |
15.txt |
AC |
104 ms |
19304 KB |
16.txt |
AC |
114 ms |
18792 KB |
17.txt |
AC |
123 ms |
18280 KB |
18.txt |
AC |
122 ms |
18536 KB |
19.txt |
AC |
104 ms |
19816 KB |
20.txt |
AC |
105 ms |
19432 KB |
21.txt |
AC |
103 ms |
17768 KB |
22.txt |
AC |
108 ms |
19432 KB |
23.txt |
AC |
72 ms |
18536 KB |
24.txt |
AC |
92 ms |
18024 KB |
25.txt |
AC |
1 ms |
256 KB |
26.txt |
AC |
1 ms |
256 KB |
s1.txt |
AC |
1 ms |
256 KB |
s2.txt |
AC |
1 ms |
256 KB |