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
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 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