Submission #1990256
Source Code Expand
// {{{
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
using namespace std;
typedef long int i32;
typedef unsigned long int u32;
typedef long long int i64;
typedef unsigned long long int u64;
typedef pair<i32, i32> PII;
typedef vector<i32> VI;
typedef vector<string> VS;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef map<i32, i32> MPII;
typedef set<i32> SETI;
typedef multiset<i32> MSETI;
#define IN(x) cin >> x;
#define SCD(t) scanf("%d",&t)
#define SCLD(t) scanf("%ld",&t)
#define SCLLD(t) scanf("%lld",&t)
#define SCC(t) scanf("%c",&t)
#define SCS(t) scanf("%s",t)
#define SCF(t) scanf("%f",&t)
#define SCLF(t) scanf("%lf",&t)
#define MEM(a, b) memset(a, (b), sizeof(a))
#define ZERO(a) memset(a, 0, sizeof(a))
#define FOR(i, j, k, in) for (int i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for (int i=j ; i>=k ; i-=in)
#define REP(i, j) FOR(i, 0, j, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define BTW(A, B, C) assert( B <= A && A <= C)
#define MP make_pair
#define PB push_back
#define PF push_front
#define INF (int)1e9
#define EPS 1e-9
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
#define DEBUG(x) cout << #x << ": " << x << endl;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
// }}}
const u32 MAX_N = 100000;
i32 x[MAX_N], y[MAX_N];
vector<pair<i32, i32>> xs;
vector<pair<i32, i32>> ys;
vector<pair<i32, i32>> e[MAX_N];
bool used[MAX_N];
inline u32 calc(i32 x1, i32 y1, i32 x2, i32 y2) {
return min(abs(x1-x2), abs(y1-y2));
}
int main() {
u32 N;
IN(N);
REP(i, N) {
cin >> x[i] >> y[i];
xs.PB(MP(x[i], i));
ys.PB(MP(y[i], i));
}
sort(ys.begin(), ys.end());
sort(xs.begin(), xs.end());
auto q = priority_queue<pair<u32, u32>, vector<pair<u32, u32>>,
greater<pair<u32, u32>>>();
used[0] = true;
u32 ans = 0;
REP(i, N-1) {
i32 x1 = xs[i].second;
i32 x2 = xs[i+1].second;
u32 cost1 = calc(x[x1], y[x1], x[x2], y[x2]);
e[x1].PB(MP(cost1, x2));
e[x2].PB(MP(cost1, x1));
i32 y1 = ys[i].second;
i32 y2 = ys[i+1].second;
u32 cost2 = calc(x[y1], y[y1], x[y2], y[y2]);
e[y1].PB(MP(cost2, y2));
e[y2].PB(MP(cost2, y1));
}
REP(i, e[0].size()) {
q.push(e[0][i]);
}
while(!q.empty()) {
auto vi = q.top();
q.pop();
auto v = vi.first;
auto index = vi.second;
if(used[index]) {
continue;
}
ans += v;
used[index] = true;
for(auto a : e[index]) {
if(used[a.second]) {
continue;
}
q.push(a);
}
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Built? |
User |
peejee0904 |
Language |
C++14 (GCC 5.4.1) |
Score |
500 |
Code Size |
3482 Byte |
Status |
AC |
Exec Time |
173 ms |
Memory |
19044 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 |
167 ms |
19044 KB |
02.txt |
AC |
164 ms |
19044 KB |
03.txt |
AC |
172 ms |
19044 KB |
04.txt |
AC |
170 ms |
19044 KB |
05.txt |
AC |
173 ms |
19044 KB |
06.txt |
AC |
168 ms |
19044 KB |
07.txt |
AC |
173 ms |
19044 KB |
08.txt |
AC |
164 ms |
19044 KB |
09.txt |
AC |
162 ms |
19044 KB |
10.txt |
AC |
160 ms |
19044 KB |
11.txt |
AC |
161 ms |
19044 KB |
12.txt |
AC |
164 ms |
19044 KB |
13.txt |
AC |
126 ms |
17764 KB |
14.txt |
AC |
128 ms |
17764 KB |
15.txt |
AC |
104 ms |
15204 KB |
16.txt |
AC |
121 ms |
15332 KB |
17.txt |
AC |
128 ms |
15204 KB |
18.txt |
AC |
123 ms |
15204 KB |
19.txt |
AC |
104 ms |
15204 KB |
20.txt |
AC |
127 ms |
18276 KB |
21.txt |
AC |
121 ms |
15204 KB |
22.txt |
AC |
117 ms |
15204 KB |
23.txt |
AC |
61 ms |
15204 KB |
24.txt |
AC |
118 ms |
16100 KB |
25.txt |
AC |
2 ms |
2560 KB |
26.txt |
AC |
2 ms |
2560 KB |
s1.txt |
AC |
2 ms |
2560 KB |
s2.txt |
AC |
2 ms |
2560 KB |