D - 道路の老朽化対策について ~サイズ付きUnion Find~

Quiz

https://atcoder.jp/contests/abc040/tasks/abc040_d

AC (verified)

https://atcoder.jp/contests/abc040/submissions/8891107

解説

  • editorialの通りですが、ポイントとしては「橋の構築」と「クエリ」を同じvectorに入れてyearでソートした後、yearの新しい方から処理していくと簡潔に書けます
  • 要素
    • Union Find
    • Query先読み
    • ソート

Code

  • いつものUnion Findクラスにサイズvectorを持たせて、uniteする時にどちらかに合成するコードを加えただけ
struct UnionFind{
    vector<ll> parent;
    VI sz;
    UnionFind(ll n){
        parent.resize(n);
        sz.resize(n, 1);
        reset();
    }

    void reset(){
        FOR(i, 0, parent.size()){
            parent[i] = i;
        }
    }

    void unite(ll a, ll b){
        if(a>b){
            swap(a, b);
        }
        ll rootA = findRoot(a);
        ll rootB = findRoot(b);
        if(rootA>rootB){
            swap(rootA, rootB);
        }
        if(rootA==rootB){
            return;
        }else{
            // 小さい方を親にする
            parent[rootB] = rootA;
            // Aが親. sizeの合体
            sz[rootA] += sz[rootB];
            sz[rootB] = 0;
        }
    }

    ll findRoot(ll a){
        if(parent[a]==a){
            return a;
        }else{
            return parent[a] = findRoot(parent[a]);
        }
    }

    map<ll, vector<ll> > getGroups(){
        map<ll, vector<ll> > G;
        FOR(i, 0, parent.size()){
            ll r = findRoot(i);
            G[r].push_back(i);
        }
        return G;
    }

    bool is_same_group(ll a, ll b){
        ll rootA = findRoot(a);
        ll rootB = findRoot(b);
        if(rootA==rootB){
            return true;
        }else{
            return false;
        }
    }
};