Submission #4025574

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;

const int inf = 1e9;
const ll linf = 1e18;
const ll mod = 1e9 + 7;

int par[100000];

int find(int x)
{
  if(par[x] == x) return x;
  return par[x] = find(par[x]);
}

void unite(int x, int y)
{
  x = find(x);
  y = find(y);
  
  if(x == y) return;

  par[x] = y;
}

bool same(int x, int y)
{
  return find(x) == find(y);
}

ll cost(int a, int b, int c, int d)
{
  return min(abs(a-c), abs(b-d));
}

int main()
{
  int n;
  cin >> n;

  vector<tuple<int, int, int> >  xy, yx;
  rep(i, n){
    int x, y;
    cin >> x >> y;
    xy.pb(mt(x, y, i));
    yx.pb(mt(y, x, i));
  }

  sort(all(xy));
  sort(all(yx));

  vector<tuple<ll, int, int> > es;
  rep(i, n-1) es.pb(mt(cost(get<0>(xy[i]), get<1>(xy[i]), get<0>(xy[i+1]), get<1>(xy[i+1])), get<2>(xy[i]), get<2>(xy[i+1])));
  rep(i, n-1) es.pb(mt(cost(get<0>(yx[i]), get<1>(yx[i]), get<0>(yx[i+1]), get<1>(yx[i+1])), get<2>(yx[i]), get<2>(yx[i+1])));

  sort(all(es));

  rep(i, n) par[i] = i;

  ll ans = 0;
  for(auto e : es){
    int x, y, c;
    tie(c, x, y) = e;
    if(!same(x, y)){
      ans += c;
      unite(x, y);
    }
  }

  cout << ans << endl;

  return 0;
}

Submission Info

Judge Result