ゆらのふなびと

競プロ, Python, C++

2016-03-04から1日間の記事一覧

SRM 679 Easy(250) FiringEmployees

「制約の有効活用」 問題 企業内の上司・部下の関係が木構造で与えられる。各従業員は自分よりも番号の若いいずれかの従業員の部下である。従業員ごとに利益の額が設定されている(これは正にも負にもなりうる)。さて、何人かの従業員を解雇することで企業の…

ABC014 D - 閉路

どこからLCAなんて発想が出てくるの!?と思った人用。 問題 木に辺を追加したときの閉路長を各クエリに対して求めよ。 制約 頂点数: クエリ数: 解法 辺 を追加したときの閉路長は、もとのグラフにおける点 と点 との最短距離を とすると、 (追加する辺の長…