hotpepsiの練習帳

SRM 682

00:40

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

Div1 Easy (300) SmilesTheFriendshipUnicorn

問題

• 友人関係の双方向のグラフが与えられる
• 友人関係を4つたどって異なる5人にたどりつけるかどうかを求める

方針

• 辺の数が少ないので、ぎりぎり全探索行けそう
• こういうのを列挙する D <- B <- A -> C -> E
• DからEまで全て異なっていればOK
• Aは全頂点で試す
• 頂点Aから行ける、異なる2頂点B,Cを全て列挙する
• DはBから行ける頂点のうち、A,C以外
• EはCから行ける頂点のうち、A,B,D以外
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_682/SmilesTheFriendshipUnicorn.cpp

結果

o-- 127.68pt 110th/280 rating 1427 -> 1490 (+63)

もっと長いのを見つけるにはcolor codingらしい

http://togetter.com/li/941933