F - Asya And Kittens

Quiz

https://codeforces.com/contest/1131/problem/F

Submit

https://codeforces.com/contest/1131/submission/50398023

Note

• 問題文の図の通り、union find木などで結合していく
• グループ毎にメンバー一覧を持っておく
• 結合した時、グループAとグループBのリストを連結する
• この時、大きいリストに小さいリストを連結するようにすると効率が良くなる
  • マージテク

リストの連結

• 事前に足される側のリストのサイズを reserve しておく必要は無かった
• std::copyも不要
• push_backでOK

戦略

• F問題ではあるが多くの人が通している
• コンテスト中にStandingsを見て多くの人が解けているならFでも取り組むべし

個人的はまりポイント

• なぜかMemory Limit Errorが取れず
• 原因はこちらのコード

void unite(ll a, ll b){
    if(findRoot(a)==findRoot(b)){
        return;
    }

    // aの方が大きいグループとする
    if(G[a].size() < G[b].size()){
        swap(a, b);
    }
...

• サイズ比較するなら、一番上の親に聞かないと
  • G[a].size() → G[findRoot(a)].size()
  • bも同様
  • これでよし
• union findは親を見つけてからparentを書き換えるなど、親がメイン
• 気をつけたい