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;
        }
    }
};