結果

問題 No.556 仁義なきサルたち
ユーザー maimai
提出日時 2017-04-17 08:16:34
言語 Text
(cat 8.3)
結果
WA  
実行時間 -
コード長 1,125 bytes
コンパイル時間 75 ms
コンパイル使用メモリ 5,400 KB
実行使用メモリ 4,508 KB
最終ジャッジ日時 2023-09-26 10:38:17
合計ジャッジ時間 1,006 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
権限があれば一括ダウンロードができます

ソースコード

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