Submission #5175749


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define REP(i,n) FOR(i,0,n)
typedef long long ll;
const ll inf = 2e9 + 7;

template <class T = int> T in() { T x; cin >> x; return (x); }

typedef pair<int, pair<int, int>> edge;

class UnionFind {
private:
	vector<int> par;
public:
	UnionFind(int N) { par = vector<int>(N, -1); }
	int find(int x);
	ll size(int x);
	void unite(int x, int y);
	bool same(int x, int y);
};



class Kruskal {
private:
	UnionFind *uf;
	vector<edge> e;
public:
	vector<edge> mst;
	Kruskal(int N) { uf = new UnionFind(N); }
	void add(int x, int y, ll z);
	void run();
};



//----UnionFind-------------------------------
int UnionFind::find(int x) {
	if (par[x] < 0) return x;
	else return par[x] = find(par[x]);
}

ll UnionFind::size(int x) {
	return -par[find(x)];
}

void UnionFind::unite(int x, int y) {
	x = find(x);
	y = find(y);

	//大きい方に小さい方をくっ付ける
	if (size(x) < size(y)) swap(x, y);
	par[x] += par[y];
	par[y] = x;
}

bool UnionFind::same(int x, int y) {
	x = find(x);
	y = find(y);
	return x == y;
}



//----Kruskal-------------------------------
void Kruskal::add(int x, int y, ll z) {
	e.push_back({ z,{x,y} });
}

void Kruskal::run() {
	sort(e.begin(), e.end());
	for (auto x : e) {
		if (uf->same(x.second.first, x.second.second)) {
			continue;
		}
		else {
			mst.push_back(x);
			uf->unite(x.second.first, x.second.second);
		}
	}
}

typedef struct {
	ll x, y;
	int I;
} pos;

//左から右へ
bool cmpx(pos &a, pos &b) {
	if (a.x != b.x) return a.x < b.x;
	else return a.y < b.y;
}

//下から上へ
bool cmpy(pos &a, pos &b) {
	if (a.y != b.y) return a.y < b.y;
	else return a.x < b.x;
}

int main() {
	int n = in();
	vector<pos> tate, yoko;
	tate = vector<pos>(n); yoko = vector<pos>(n);
	REP(i, n) {
		yoko[i].I = tate[i].I = i;
		yoko[i].x = tate[i].x = in();
		yoko[i].y = tate[i].y = in();
	}
	sort(yoko.begin(), yoko.end(), cmpx);
	sort(tate.begin(), tate.end(), cmpy);
	Kruskal ks(n);
	ks.add(yoko[0].I, yoko[1].I, min(abs(yoko[1].x - yoko[0].x), abs(yoko[1].y - yoko[0].y)));
	ks.add(yoko[n - 1].I, yoko[n - 2].I, min(abs(yoko[n - 1].x - yoko[n - 2].x), abs(yoko[n - 1].y - yoko[n - 2].y)));
	ks.add(tate[0].I, tate[1].I, min(abs(tate[1].x - tate[0].x), abs(tate[1].y - tate[0].y)));
	ks.add(tate[n - 1].I, tate[n - 2].I, min(abs(tate[n - 1].x - tate[n - 2].x), abs(tate[n - 1].y - tate[n - 2].y)));
	FOR(i, 1, n - 1) {
		ks.add(yoko[i].I, yoko[i - 1].I, min(abs(yoko[i].x - yoko[i - 1].x), abs(yoko[i].y - yoko[i - 1].y)));
		ks.add(yoko[i].I, yoko[i + 1].I, min(abs(yoko[i].x - yoko[i + 1].x), abs(yoko[i].y - yoko[i + 1].y)));
		ks.add(tate[i].I, tate[i - 1].I, min(abs(tate[i].x - tate[i - 1].x), abs(tate[i].y - tate[i - 1].y)));
		ks.add(tate[i].I, tate[i + 1].I, min(abs(tate[i].x - tate[i + 1].x), abs(tate[i].y - tate[i + 1].y)));
	}
	ks.run();
	ll ans = 0;
	for (auto x : ks.mst) {
		ans += x.first;
	}
	cout << ans << endl;
}

Submission Info

Submission Time
Task D - Built?
User harady
Language C++14 (GCC 5.4.1)
Score 500
Code Size 3101 Byte
Status
Exec Time 165 ms
Memory 14060 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt
All 500 / 500 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 154 ms 12784 KB
02.txt 154 ms 13552 KB
03.txt 155 ms 13676 KB
04.txt 155 ms 13552 KB
05.txt 154 ms 13292 KB
06.txt 153 ms 13552 KB
07.txt 165 ms 12912 KB
08.txt 153 ms 13164 KB
09.txt 152 ms 13168 KB
10.txt 152 ms 13040 KB
11.txt 153 ms 13552 KB
12.txt 151 ms 13040 KB
13.txt 128 ms 13424 KB
14.txt 128 ms 13168 KB
15.txt 128 ms 13548 KB
16.txt 144 ms 13804 KB
17.txt 154 ms 13548 KB
18.txt 146 ms 13552 KB
19.txt 128 ms 12912 KB
20.txt 128 ms 14060 KB
21.txt 130 ms 13932 KB
22.txt 132 ms 13292 KB
23.txt 75 ms 13804 KB
24.txt 124 ms 13932 KB
25.txt 1 ms 256 KB
26.txt 1 ms 256 KB
s1.txt 1 ms 256 KB
s2.txt 1 ms 256 KB