Submission #1841304
Source Code Expand
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define EACH(i, c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
//#define LOCAL 0
//#ifdef LOCAL
//#define DEBUG(s) cout << (s) << endl
//#define dump(x) cerr << #x << " = " << (x) << endl
//#define BR cout << endl;
//#else
//#define DEBUG(s) do{}while(0)
//#define dump(x) do{}while(0)
//#define BR
//#endif
//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 20)
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x) cerr << #x << " = " << (x) << endl
//ここから編集する
///クラスカル法
struct edge {int u,v;ll cost;};
bool comp(const edge& e1,const edge& e2){
return e1.cost < e2.cost;
}
vector<edge> es;
///クラスカル法ここまで
class UnionFind {
vector<int> p;//p[i]はiの属する組織
public:
UnionFind(int n){
p = vector<int>(n);
for(int i = 0; i < n; i++){
p[i] = i;
}
return;
}
void printState() {
if (DEBUG) {
cout << "---" << endl;
for (int i = 0; i < p.size(); i++) {
printf("%dの親は%d\n", i, p[i]);
}
cout << "---" << endl;
}
}
/* xの属する集合を返す */
int find(int x) {
if (p[x] == x) return x;
return p[x] = find(p[x]);
}
/* yにxを統合する */
void unite(int x, int y) {
p[find(x)] = p[find(y)];
}
/* xとyが属する集合が同じかを判定する */
bool same(int x, int y) {
return find(x) == find(y);
}
};
int main() {
int N;
cin >> N;
vector<pair<ll,int> > x(N);
vector<pair<ll,int> > y(N);
rep(i,0,N){
int xx,yy;
cin >> xx >> yy;
x[i] = make_pair(xx,i);
y[i] = make_pair(yy,i);
}
sort(all(x));
sort(all(y));
rep(i,0,x.size()-1){
edge e{};
e.u = x[i].second;
e.v = x[i+1].second;
e.cost = abs(x[i].first - x[i+1].first);
es.push_back(e);
swap(e.u,e.v);
es.push_back(e);
}
rep(i,0,y.size()-1){
edge e{};
e.u = y[i].second;
e.v = y[i+1].second;
e.cost = abs(y[i].first - y[i+1].first);
es.push_back(e);
swap(e.u,e.v);
es.push_back(e);
}
sort(all(es),comp);
UnionFind u(N);
ll ans = 0LL;
for(int i = 0; i < es.size(); i++){
edge e = es[i];
if(!u.same(e.u,e.v)){
u.unite(e.u,e.v);
ans += e.cost;
}
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Built? |
User |
homesentinel |
Language |
C++14 (GCC 5.4.1) |
Score |
500 |
Code Size |
3530 Byte |
Status |
AC |
Exec Time |
148 ms |
Memory |
13676 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 |
146 ms |
12908 KB |
02.txt |
AC |
146 ms |
12524 KB |
03.txt |
AC |
146 ms |
13548 KB |
04.txt |
AC |
146 ms |
11756 KB |
05.txt |
AC |
146 ms |
13036 KB |
06.txt |
AC |
147 ms |
13548 KB |
07.txt |
AC |
148 ms |
13420 KB |
08.txt |
AC |
147 ms |
13676 KB |
09.txt |
AC |
140 ms |
13420 KB |
10.txt |
AC |
140 ms |
12652 KB |
11.txt |
AC |
140 ms |
12012 KB |
12.txt |
AC |
140 ms |
12268 KB |
13.txt |
AC |
104 ms |
13420 KB |
14.txt |
AC |
104 ms |
13292 KB |
15.txt |
AC |
94 ms |
11884 KB |
16.txt |
AC |
107 ms |
13292 KB |
17.txt |
AC |
116 ms |
13548 KB |
18.txt |
AC |
112 ms |
13164 KB |
19.txt |
AC |
97 ms |
11884 KB |
20.txt |
AC |
97 ms |
12524 KB |
21.txt |
AC |
96 ms |
11756 KB |
22.txt |
AC |
102 ms |
13164 KB |
23.txt |
AC |
63 ms |
13420 KB |
24.txt |
AC |
86 ms |
11884 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 |