hotpepsiの練習帳

SRM 618

着想 | 01:56

Div1 Easy (250) Family

問題

• 簡易版の家系図がある
• 配列parent1とparent2があり、親のindexが入っている
• 親は片方が男で片方が女である
• 可能な組み合わせかどうかを求める

方針

• ひとつの組み合わせを決めたら、あとは再帰的に決めていって矛盾があるかどうかを見ればよさそう
• なんとか提出
• Passed System Test
• union findに突っ込んで矛盾があるかどうかを見ればよかった
• AとBがCの親で、AとDがEの親みたいなとき、BとDは同じ性別みたいにしてグルーピングして、矛盾があればNG
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_618/Family.cpp

結果

o-- +1 99.96 + 50 = 149.96pt 320th/532 rating 1544 -> 1528 (-16)

久々のunion find回。

http://togetter.com/li/659154