Submission #3017540
Source Code Expand
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<set>
#include<map>
#include<bitset>
using namespace std;
typedef long long ll;
#define i_7 1000000007
#define i_5 1000000005
ll mod(ll a){
ll c=a%i_7;
if(c>=0)return c;
else return c+i_7;
}
typedef pair<int,int> i_i;
typedef pair<ll,ll> l_l;
ll inf=1000000000000;/*10^12*/
#define rep(i,l,r) for(ll i=l;i<=r;i++)
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
//////////////////////////////////////
#define MAX_N 1000000//調節!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
int par[MAX_N],dep[MAX_N];//depはrankのこと
//n要素で初期化
void init(int n){
for(int i=0;i<=n-1;i++){
par[i]=i;
dep[i]=0;
}
}
//木の根を求める
int find(int x){
return par[x]==x?x:par[x]=find(par[x]);
}
//xとyの属する集合を併合
void unite(int x,int y){
x=find(x);
y=find(y);
if(x==y)return;
if(dep[x]<dep[y]){
par[x]=y;
}else{
par[y]=x;
if(dep[x]==dep[y])dep[x]++;
}
}
//xとyが同じ集合に属するか否か
bool same(int x,int y){
return find(x)==find(y);
}
//////////////////////////////////////
struct edge{int u,v,cost;};
bool comp(const edge& e1,const edge& e2){
return e1.cost<e2.cost;
}
#define MAX_E 1000000//調節!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
edge es[MAX_E];
int v,e;//頂点数vと辺数e
int kruskal(){
sort(es,es+e,comp);
init(v);
int res=0;
for(int i=0;i<e;i++){
edge e=es[i];
if(!same(e.u,e.v)){
unite(e.u,e.v);
res+=e.cost;
}
}
return res;
}
///////////////////////////////////////////
struct point{
i_i xy;
int num;
};
bool comp1(point x,point y){
return x.xy.first<y.xy.first;
}
bool comp2(point x,point y){
return x.xy.second<y.xy.second;
}
int main(){
cin>>v;
e=2*v-2;
point pp[v];
rep(i,0,v-1){
pp[i].num=i;
cin>>pp[i].xy.first>>pp[i].xy.second;
}
sort(pp,pp+v,comp1);
rep(i,0,v-2){
es[i].u=pp[i].num;
es[i].v=pp[i+1].num;
es[i].cost=pp[i+1].xy.first-pp[i].xy.first;
}
sort(pp,pp+v,comp2);
rep(i,0,v-2){
es[v-1+i].u=pp[i].num;
es[v-1+i].v=pp[i+1].num;
es[v-1+i].cost=pp[i+1].xy.second-pp[i].xy.second;
}
cout<<kruskal()<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Built? |
User |
sugarrr |
Language |
C++14 (GCC 5.4.1) |
Score |
500 |
Code Size |
2830 Byte |
Status |
AC |
Exec Time |
154 ms |
Memory |
9600 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 |
152 ms |
9600 KB |
02.txt |
AC |
154 ms |
9600 KB |
03.txt |
AC |
152 ms |
9600 KB |
04.txt |
AC |
154 ms |
9600 KB |
05.txt |
AC |
152 ms |
9600 KB |
06.txt |
AC |
154 ms |
9600 KB |
07.txt |
AC |
152 ms |
9600 KB |
08.txt |
AC |
153 ms |
9600 KB |
09.txt |
AC |
147 ms |
9600 KB |
10.txt |
AC |
149 ms |
9600 KB |
11.txt |
AC |
147 ms |
9600 KB |
12.txt |
AC |
147 ms |
9600 KB |
13.txt |
AC |
105 ms |
9600 KB |
14.txt |
AC |
104 ms |
9600 KB |
15.txt |
AC |
100 ms |
9600 KB |
16.txt |
AC |
116 ms |
9600 KB |
17.txt |
AC |
131 ms |
9600 KB |
18.txt |
AC |
125 ms |
9600 KB |
19.txt |
AC |
100 ms |
9600 KB |
20.txt |
AC |
100 ms |
9600 KB |
21.txt |
AC |
100 ms |
9600 KB |
22.txt |
AC |
106 ms |
9600 KB |
23.txt |
AC |
59 ms |
9600 KB |
24.txt |
AC |
81 ms |
9600 KB |
25.txt |
AC |
2 ms |
4352 KB |
26.txt |
AC |
2 ms |
4352 KB |
s1.txt |
AC |
2 ms |
4352 KB |
s2.txt |
AC |
2 ms |
4352 KB |