AtCoder Beginner Contest 065D

D - Built?

余分に辺を追加する必要はないから，最小全域木を求めればよい．

このままだと辺の本数がO(N^2)であるから，辺を減らすことを考える．

隣同士の辺しか使う必要がないため，辺の本数がO(N)となって間に合う．

実装は，tupleを用いて

<x,y,index> , <y,x,index>

を lex order でソートすれば，隣同士の辺が得られる．最後にindexを追加しているのは，ソートしたときに元のindex が失われてしまうため，記録しておく．

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

using vll = vector<long long>;  using vvll = vector<vll>;

using pll = pair<ll,ll>;

int main() {

    ll n, m, k, q;

    cin >> n;

    using T = tuple<ll,ll,ll>; // {x,y,ind} or {y,x,ind}

    vector<T> a[2];

    rep(i,n){

        ll x,y; cin>>x >> y;

        a[0].push_back({x,y,i});

        a[1].push_back({y,x,i});

    }

    sort(all(a[0]));

    sort(all(a[1]));

    vector<T> ed; // {cost, cu, ne}

    rep(s,2){

        rep(i,n-1){

            T cu = a[s][i];

            T ne = a[s][i+1];

            ll cx, cy, ci;

            ll nx, ny, ni;

            tie(cx,cy,ci) = cu;

            tie(nx,ny,ni) = ne;

            ed.push_back({abs(nx-cx), ci, ni});

            ed.push_back({abs(nx-cx), ni, ci});

        }

    }

    UnionFind<ll> uf(n);

    sort(all(ed));

    ll ans = 0;

    for(auto [co, q, r]:ed){

        if(!uf.same(q,r)){

            ans += co;

            uf.merge(q,r);

        }

    }

    cout << ans << endl;

    return 0;

}