Submission #1994769


Source Code Expand

Copy
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<(n);i++)
#define loop(i,a,n) for(i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef pair<int,int> pii;

#define MAX_N 100005

int parent[MAX_N];
int ran[MAX_N];

void init(int n){
    int i;
    rep(i,n){
        parent[i]=i;
        ran[i]=0;
    }
}

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(ran[x]<ran[y])
        parent[x]=y;
    else{
        parent[y]=x;
        if(ran[x]==ran[y])ran[x]++;
    }
}

struct edge{ int u,v,cost;};

bool comp(const edge& e1, const edge& e2){
    return e1.cost < e2.cost;
}

edge es[2*MAX_N];
int v,e=0;

int kruskal(){
    sort(es,es+e,comp);
    init(v);
    int res=0,i;
    rep(i,e){
        edge e=es[i];
        if(find(e.u) != find(e.v)){
            unite(e.u,e.v);
            res+=e.cost;
        }
    }
    return res;
}

int main(void) {
    int i,j;
    int n;
    cin>>n;
    v=n;

    vector<pair<pii,int> > p(n);
    rep(i,n)cin>>p[i].first.first>>p[i].first.second,p[i].second=i;

    sort(all(p));
    rep(i,n-1){
        es[e].u=p[i].second;
        es[e].v=p[i+1].second;
        es[e].cost=min(abs(p[i].first.first-p[i+1].first.first), abs(p[i].first.second-p[i+1].first.second));
        e++;
    }
    rep(i,n)swap(p[i].first.first,p[i].first.second);
    sort(all(p));
    rep(i,n-1){                 
         es[e].u=p[i].second;              
         es[e].v=p[i+1].second;
         es[e].cost=min(abs(p[i].first.first-p[i+1].first.first), abs(p[i].first.second-p[i+1].first.second));
         e++;
    }

    cout<<kruskal()<<endl;
}

Submission Info

Submission Time
Task D - Built?
User rika0384
Language C++14 (GCC 5.4.1)
Score 500
Code Size 2238 Byte
Status
Exec Time 118 ms
Memory 4480 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 117 ms 4480 KB
02.txt 117 ms 4480 KB
03.txt 117 ms 4480 KB
04.txt 117 ms 4480 KB
05.txt 118 ms 4480 KB
06.txt 117 ms 4480 KB
07.txt 117 ms 4480 KB
08.txt 117 ms 4480 KB
09.txt 113 ms 4480 KB
10.txt 113 ms 4480 KB
11.txt 113 ms 4480 KB
12.txt 113 ms 4480 KB
13.txt 78 ms 4480 KB
14.txt 78 ms 4480 KB
15.txt 76 ms 4480 KB
16.txt 88 ms 4480 KB
17.txt 96 ms 4480 KB
18.txt 94 ms 4480 KB
19.txt 76 ms 4480 KB
20.txt 76 ms 4480 KB
21.txt 76 ms 4480 KB
22.txt 81 ms 4480 KB
23.txt 52 ms 4480 KB
24.txt 72 ms 4480 KB
25.txt 3 ms 384 KB
26.txt 1 ms 256 KB
s1.txt 1 ms 256 KB
s2.txt 1 ms 256 KB