【ABC409】F問題 - Connecting Points 考察から実装(c++)まで

AtCoderBeginnerContest409の解説＆感想です。
コンテストリンク

問題一覧

• 【ABC409】A問題 - Conflict　考察から実装(c++)まで
• 【ABC409】B問題 - Citation　考察から実装(c++)まで
• 【ABC409】C問題 - Equilateral Triangle　考察から実装(c++)まで
• 【ABC409】D問題 - String Rotation　考察から実装(c++)まで
• 【ABC409】E問題 - Pair Annihilation　考察から実装(c++)まで
• 【ABC409】F問題 - Connecting Points　考察から実装(c++)まで <- イマココ

F問題 - Connecting Points

問題リンク

問題概要

二次元平面上に、$N$頂点$0$辺のグラフ$G$がある。$G$の二点間の距離をマンハッタン距離で定義する。
また、$G$の連結成分$A,B$の距離を、$A$の点と$B$の点の中で一番近い二点間の距離と定義する。
以下の三種類のクエリを$Q$回処理せよ。

• 1 a b : $G$に頂点$(a,b)$を追加する。
• 2
  • $G$の異なる二つの連結成分で、距離が最小のもの全てをマージし、その最小の距離を表示する。
  • $G$の連結成分が1つしかないときは-1を表示する。
• 3 u v : 頂点$u,v$が同じ連結成分にあればYes、違う連結成分に属していたらNoを表示する。

制約

• $ 2 \le N \le 1500 $
• $ 1 \le Q \le 1500 $
• $ 0 \le x_i,y_i \le 10^9 $

考察

かなり素直に考えればいい。
とりあえず連結成分どうたらの問題で、切り離しがないので、UnionFindで管理すれば良さそう。

現状の全ての連結成分間の距離を常に持っておいて、priority_queueで小さい順に取り出す、とかでできそう。
クエリの数は$1500$以下で元々の頂点数も$1500$以下なので、出来得る連結成分の個数は最大でも$3000$個。
ということは、連結成分同士の組み合わせの数は最大でも$9 \times 10^6$。やっぱクエリ1で頂点が追加されるたびに、今までの連結成分ぜんぶとの距離をpriority_queueに突っ込んでいけばよさそう！

計算量は$O((N+Q)^2 log (N+Q))$

実装

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll,ll>;
using vll = vector<ll>;
using vpll = vector<pll>;

struct UnionFind {
public:
    vll par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
    vll kosu;
    ll Count; //全体として何個の集合があるか
    
    UnionFind(ll n) : par(n),kosu(n),Count(n) { //最初は全てが根であるとして初期化
        for(int i=0;i<n;i++){
            par[i] = i;
            kosu[i] = 1;
        }
    }

    ll root(ll x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(ll x, ll y) { // xとyの木を併合
        ll rx = root(x); //xの根をrx
        ll ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根
        kosu[ry] += kosu[rx];
        Count--;
    }

    bool same(ll x, ll y) { // 2つのデータx, yが属する木が同じならtrueを返す
        ll rx = root(x);
        ll ry = root(y);
        return rx == ry;
    }
    
    ll size(ll x){
        return kosu[root(x)];
    }
    ll size(){
        return Count;
    }
};

//(頂点iとjの距離がd)という情報を保持しておくための構造体
struct S{
    ll d,i,j;
    
    bool operator<(const S &other) const {
        return this->d > other.d;
    }
};

ll distance(pll a, pll b){
    return abs(a.first - b.first) + abs(a.second - b.second);
}

int main(void){
    //入力
    ll N,Q;
    cin>>N>>Q;
    
    vpll points(N);
    for(int i=0;i<N;i++) cin>>points[i].first>>points[i].second;
    
    //頂点数は最大でも3000個なので、3000用意しておけばいい
    UnionFind uf(3000);
    
    //頂点間の距離が小さい順に取り出すやつ
    priority_queue<S> q;
    for(int i=0;i<N;i++){
        for(int j=i+1;j<N;j++){
            q.push(S{distance(points[i], points[j]), i,j});
        }
    }
    
    while(Q--){
        ll t;
        cin>>t;
        if(t == 1){
            //新しく追加された頂点と、今までの頂点との距離を優先度付きキューに入れていく
            ll a,b;
            cin>>a>>b;
            for(int i=0;i<points.size();i++){
                q.push(S{distance(points[i], {a,b}), i, (ll)points.size()});
            }
            points.push_back({a,b});
        }
        else if(t == 2){
            //違う頂点間の点がなければ、-1
            if(q.empty()){
                cout<<-1<<endl;
                continue;
            }
            ll mi = q.top().d;
            //距離が最小のやつらを全部くっつけていく
            while(!q.empty() && q.top().d == mi){
                uf.unite(q.top().i, q.top().j);
                q.pop();
            }
            //すでに同じ連結成分のやつは消していく
            while(!q.empty() && uf.same(q.top().i, q.top().j)) q.pop();
            
            cout<<mi<<endl;
        }
        else{
            //頂点u,vが同じ連結成分かどうかを、UnionFindを使って確認
            ll u,v;
            cin>>u>>v;
            cout<<(uf.same(u-1, v-1)?"Yes":"No")<<endl;
        }
    }
    return 0;
}