Contest Duration: ~ (local time) (100 minutes) Back to Home

Submission #3924290

Source Code Expand

Copy
#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("Yes")
#define p_no() p("No")

const ll mod = 1e9 + 7;
const ll inf = 1e18;

struct Point{
ll x;
ll y;
ll id;
Point(ll x, ll y, ll id): x(x), y(y), id(id) {}

static bool sortByX(Point a, Point b){
if(a.x == b.x){
return a.y < a.y;
}else{
return a.x < b.x;
}
}

static bool sortByY(Point a, Point b){
if(a.y == b.y){
return a.x < a.x;
}else{
return a.y < b.y;
}
}
};

struct Edge{
ll from;
ll to;
ll cost;

static bool sortByCost(Edge a, Edge b){
return a.cost < b.cost;
}
};

const int N_MAX = 100010;
int parent[N_MAX] = {};
vector<Point> P;
vector<Edge> edgeList;

ll findRoot(ll x){
if(parent[x] == x){
return x;
}else{
auto root = findRoot(parent[x]);
parent[x] = root; // path compression
return root;
}
}

void _union(ll a, ll b){
auto rootA = findRoot(a);
auto rootB = findRoot(b);

if(rootA == rootB){
return;
}else{
parent[a] = b;
}
}

int main(){
cin.tie(0);
ios::sync_with_stdio(false);

// input
ll N;
cin >> N;

P.reserve(N);

FOR(i, 0, N){
ll x, y;
cin >> x >> y;
Point p = Point(x, y, i);
P.push_back(p);
}

sort(ALL(P), Point::sortByX);
FOR(i, 0, N-1){
Edge edge;
edge.from = P[i].id;
edge.to = P[i+1].id;
edge.cost = min(abs(P[i].x - P[i+1].x), abs(P[i].y - P[i+1].y));
edgeList.push_back(edge);
}

sort(ALL(P), Point::sortByY);
FOR(i, 0, N-1){
Edge edge;
edge.from = P[i].id;
edge.to = P[i+1].id;
edge.cost = min(abs(P[i].x - P[i+1].x), abs(P[i].y - P[i+1].y));
edgeList.push_back(edge);
}

sort(ALL(edgeList), Edge::sortByCost);

// make MST by kruskal
FOR(i, 0, N_MAX){
parent[i] = i;
}

ll cost_sum = 0;

// 短いエッジから見ていって必要なら連結
for(auto edge : edgeList){

if(findRoot(edge.from) == findRoot(edge.to)){
// skip
}
else{
// つなぐ
_union(findRoot(edge.from), findRoot(edge.to));
cost_sum += edge.cost;
}
}

p(cost_sum);

return 0;
}

Submission Info

Submission Time 2019-01-04 05:47:42+0900 D - Built? peroon C++14 (GCC 5.4.1) 500 2857 Byte AC 86 ms 10736 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
 AC × 2
 AC × 28
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 86 ms 9712 KB
02.txt 85 ms 10608 KB
03.txt 84 ms 10480 KB
04.txt 84 ms 10608 KB
05.txt 86 ms 9328 KB
06.txt 85 ms 10736 KB
07.txt 85 ms 9968 KB
08.txt 84 ms 10736 KB
09.txt 82 ms 10352 KB
10.txt 83 ms 9584 KB
11.txt 83 ms 9200 KB
12.txt 82 ms 10480 KB
13.txt 57 ms 10352 KB
14.txt 57 ms 10352 KB
15.txt 58 ms 9328 KB
16.txt 59 ms 9712 KB
17.txt 60 ms 8944 KB
18.txt 61 ms 9328 KB
19.txt 58 ms 10224 KB
20.txt 60 ms 9200 KB
21.txt 59 ms 9840 KB
22.txt 60 ms 10096 KB
23.txt 45 ms 10096 KB
24.txt 57 ms 10736 KB
25.txt 2 ms 640 KB
26.txt 2 ms 640 KB
s1.txt 2 ms 640 KB
s2.txt 1 ms 640 KB