2013-06-01から1ヶ月間の記事一覧

2013年JOI春合宿4日目 宇宙船(SpaceShips)

問題文が「これ木構造だから!木構造だからね!そこんとこよろしく!」と語りかけてくる問題. 概要 N個の星があって,それぞれの星は1つの宇宙船を保有している.ある星aが保有している宇宙船を別の星bに向かわせるとき人を乗せていくことができるが,帰り…

LinkCut木を実装してみた

LinkCut木について勉強する機会があったので@iwiwi先生のスライドと,Tarjanの本(邦訳は絶版っぽい.そして原著高いので誰か買ってください)を参考に実装してみた.LinkCut木は,木をパスに分解して木にして,それに含まれるパスをSplay木で管理するというよ…