結果

問題 No.556 仁義なきサルたち
ユーザー mai
提出日時 2017-04-17 08:16:34
言語 Text
(cat 8.3)
結果
WA  
実行時間 -
コード長 1,125 bytes
コンパイル時間 77 ms
コンパイル使用メモリ 5,248 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-19 05:22:44
合計ジャッジ時間 796 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

ここにtesterの解説を書きます．


想定解はUnion-Find Algorithmを問題用に改造したものです．


Union-Findとは，次のような操作が出来るデータ構造です．

  union操作(x,y): xが入っている集合とyが入っている集合を結合する．
  find判定(x,y) : xとyが同じ集合に入っているかどうか判定する．

ここではUnion-Findの実装の解説はしないので，蟻本81ページや他ウェブサイトを参照してください．
http://www.prefield.com/algorithm/container/union_find.html


『Union-Findを貼るだけ問題』のように見えますが，
Union-Findの実装は計算量をなるべく減らすため，少ない方にマージしようとします．

しかし問題文では『猿の群れは数が多い方にマージされる』的な何かが書かれているので，
union操作の実装を題意に合わせるよう書き直す必要があります．


あとはシミュレートするだけです．


最悪計算量のオーダーは見積もれていないのでかしこーい人お願いします．
0