AtCoder Beginner Contest 065 D - Built?

解説ACしました...

問題

atcoder.jp

解法

解説の通り、愚直に考えると頂点本の辺からなる最小全域木を解くことが思いつくが、という制約下ではTLEしてしまう。しかし、x座標またはy座標で座標をソートした時、2つ以上離れた点同士のみを結ぶ辺のコストでその2つの点に加えて間の点を全て結ぶことができてしまうので、隣同士のみ辺を結べば十分であることが分かる。

結局これら本のエッジを張った後に最小全域木をクラスカル法などによって解けば十分実行時間制限に間に合う。2つの要素を一方の値でソートしたいときにはpairの配列を使えばよい。

コード

#include <bits/stdc++.h>
using namespace std;
struct union_find
{
    vector<long long> par;  //親の番号　
    vector<long long> rank; //木の深さ(根のランクは0)
    vector<long long> siz;  //要素xが根なら木の頂点数を格納する
    //初期化子リストを用いた初期化
    union_find(long long N) : par(N), rank(N), siz(N)
    {
        for (long long i = 0; i < N; i++)
        {
            par[i] = i;
            rank[i] = 0;
            siz[i] = 1;
        }
    }
    //要素xが所属する木の根を再帰的に発見する
    long long root(long long x)
    {
        if (par[x] == x)
            return x;
        return par[x] = root(par[x]); //経路圧縮
    }
    //要素xが属する木と要素yが属する木の併合
    void unite(long long x, long long y)
    {
        long long rx = root(x);
        long long ry = root(y);
        if (rx == ry)
            return; //同じ木に属してたらそのまま
        if (rank[rx] < rank[ry])
        {
            par[rx] = ry; //根がryの木に併合
            siz[ry] = siz[rx] + siz[ry];
        }
        else
        {
            par[ry] = rx; //根がrxの木に併合
            siz[rx] = siz[rx] + siz[ry];
            if (rank[rx] == rank[ry])
                rank[rx]++;
        }
    }
    //要素xが属する木と要素yが属する木が同じならtrueを返す
    bool same(long long x, long long y)
    {
        return root(x) == root(y);
    }
    //要素xが属する木の頂点数を返す
    long long size(long long x)
    {
        return siz[root(x)];
    }
};
/*
クラスカル法
kruskal(V,E):無向グラフから最小全域木を作り使われる辺のコストを返す
使用するためにはunion_findが必要
計算量O(ElogV)
*/
struct kruskal_edge
{
    long long u;
    long long v;
    long long cost;
};
//辺のコストの大小を比較
bool kruskal_comp(const kruskal_edge &e1, const kruskal_edge &e2)
{
    return e1.cost < e2.cost;
}
vector<kruskal_edge> kruskal_side;
long long kruskal(long long V, long long E) //V:頂点数,E:辺数
{
    sort(kruskal_side.begin(), kruskal_side.end(), kruskal_comp); //辺のコストが小さい順にソート
    union_find kruskal_tree(V);
    long long kruskal_res = 0;
    for (long long i = 0; i < E; i++)
    {
        kruskal_edge ks = kruskal_side[i];
        if (!kruskal_tree.same(ks.u, ks.v))
        {
            kruskal_tree.unite(ks.u, ks.v);
            kruskal_res += ks.cost;
        }
    }
    return kruskal_res;
}
typedef long long ll;
int main()
{
    cout << fixed << setprecision(10);
    ll N;
    cin >> N;
    kruskal_side.resize(2 * (N - 1)); //edgeの本数だけ確保
    map<pair<ll, ll>, ll> field;      //ソート後に座標から頂点の番号を特定するのに必要
    vector<pair<ll, ll>> xpairs(N);   //x座標でソート用
    vector<pair<ll, ll>> ypairs(N);   //y座標でソート用
    for (ll i = 0; i < N; i++)
    {
        ll a, b;
        cin >> a >> b;
        pair<ll, ll> P = make_pair(a, b), Q = make_pair(b, a);
        field[P] = i;
        xpairs[i] = P;
        ypairs[i] = Q;
    }
    sort(xpairs.begin(), xpairs.end());
    sort(ypairs.begin(), ypairs.end());
    ll now = 0;
    for (ll i = 0; i < N - 1; i++)
    {
        //xpairs
        kruskal_side[now].u = field[xpairs[i]];
        kruskal_side[now].v = field[xpairs[i + 1]];
        kruskal_side[now].cost = xpairs[i + 1].first - xpairs[i].first;
        now++;
        //ypairs
        //x座標とy座標を交換したものを用意(番号特定用に)
        pair<ll, ll> alter1 = make_pair(ypairs[i].second, ypairs[i].first);
        pair<ll, ll> alter2 = make_pair(ypairs[i + 1].second, ypairs[i + 1].first);
        kruskal_side[now].u = field[alter1];
        kruskal_side[now].v = field[alter2];
        kruskal_side[now].cost = ypairs[i + 1].first - ypairs[i].first;
        now++;
    }
    cout << kruskal(N, 2 * (N - 1)) << endl;
    return 0;
}