Submission #2717223

---

Source Code Expand

#include <bits/stdc++.h>
#define INF 1000000000
#define debug(x) cerr << #x << ": " << x << '\n';
using namespace std;
using ll = long long;
using P = pair<int, int>;
using PP = pair<P, int>;

class UnionFindTree{
	private:
		int N;
		unique_ptr<int[]> parent;
		unique_ptr<int[]> rank;
		unique_ptr<int[]> size;
	public:
		UnionFindTree(int N){
			this -> N = N;
			this -> parent = make_unique<int[]>(N);
			this -> rank = make_unique<int[]>(N);
			this -> size = make_unique<int[]>(N);
			for(int i = 0; i < (int) N; i++){
				parent[i] = i; rank[i] = 0; size[i] = 1;
			}
		}
		void init(){
			for(int i = 0; i < (int) N; i++){
				parent[i] = i; rank[i] = 0; size[i] = 1;
			}
		}
		int find(int x){
			if(parent[x] == x) return x;
			else return parent[x] = find(parent[x]);
		}
		void unite(int x, int y){
			x = find(x); y = find(y);
			if(x == y) return;

			if(rank[x] < rank[y]){
				parent[x] = y;
				size[y] += size[x];
			}else{
				parent[y] = x;
				size[x] += size[y];
				if(rank[x] == rank[y]) rank[x]++;
			}
		}
		bool same(int x, int y){
			return find(x) == find(y);
		}
		int count(int x){
			return size[find(x)];
		}
};

struct edge{
	int from, to, cost;
};

bool comp(PP p1, PP p2){
	return p1.first.second < p2.first.second;
}

bool compEdge(edge e1, edge e2){
	return e1.cost < e2.cost;
}

int main(void){
	int N; cin >> N;
	vector<PP> points(N);
	for(int i = 0; i < N; i++){
		cin >> points[i].first.first >> points[i].first.second;
		points[i].second = i;
	}

	sort(begin(points), end(points));
	vector<edge> G;
	for(int i = 0; i < N-1; i++){
		PP p1 = points[i], p2 = points[i+1];
		int c = min(abs(p1.first.first - p2.first.first), abs(p1.first.second - p2.first.second));
		edge e = {p1.second, p2.second, c};
		G.push_back(e);
	}

	sort(begin(points), end(points), comp);
	for(int i = 0; i < N-1; i++){
		PP p1 = points[i], p2 = points[i+1];
		int c = min(abs(p1.first.first - p2.first.first), abs(p1.first.second - p2.first.second));
		edge e = {p1.second, p2.second, c};
		G.push_back(e);
	}

	UnionFindTree uf(N);
	sort(begin(G), end(G), compEdge);
	ll res = 0;
	for(int i = 0; i < (int)G.size(); i++){
		edge e = G[i];
		if(not uf.same(e.from, e.to)){
			uf.unite(e.from, e.to);
			res += e.cost;
		}
	}

	cout << res << '\n';

	return 0;
}

Submission Info

Judge Result