hotpepsiの練習帳

SRM 674

01:16

https://competitiveprogramming.info/topcoder/srm/round/16624/div/1

Div1 Easy (250) VampireTree

問題

• バンパイアは、人間をバンパイアに変化させることで生まれる
• その変化の際、もともとのバンパイアがマスターに、元人間はサーバントとなる
• バンパイアから別のバンパイアへ、マスターまたはサーバントへ1つずつたどった最小の回数を距離とする
• バンパイアの親子関係が与えられる
• マスターを持たないバンパイアが一つだけ存在する
• 親子関係に矛盾がない場合、バンパイアの距離の最大値を求める

方針

• (終了後)
• たぶん木
• 木のとき、辺を2以上持つノードを移動していく
• 葉から辺を2以上持つノードを経由して葉に至るので、葉が2つ以上あるノード数+1が答え
• 木でなければ-1
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_674/VampireTree.cpp

結果

--- 0pt 181st/316 rating 1219 -> 1219 (+0)

サーバントが直接の子のみを指す、というのは最後の長いサンプルをよく読むとわかるようになっていたが、どのみちシンプルな解法を見つけるのが難しかった。

AC率が低くDiv2落ち回避。

http://togetter.com/li/907146