きろく

特筆すべき記録のまとめ

yukicoder:No.812 Change of Class

問題

yukicoder.me

解法

まず,各クエリで与えられる頂点を始点としてダイクストラ法を用いて全頂点への最短距離を求める.ここで,到達できる頂点の数が最大の友達の数になる.

次に,各頂点と始点の頂点が何日で友達になるかを調べる.1 日目には 0 日目に友達であった人が友達である人(友達の友達)と友達になる.2 日目には 1 日目に新しく友達になった人が 1 日目の時点で友達である人と友達になる.ここで,友達である頂点との距離の最大の推移を実験して観察すると,最初は距離 1 以内の人だけだったのが距離 2, 4, 8, ... と 2 倍ずつ距離が伸びていく.よって,距離 d の頂点と友達になるには log2(d) 日必要だと分かる(d = 0 のときは当然 0 日).あとはこの計算結果の max を取り,答えとすればよい.O(Q * N * logM).

解答

yukicoder.me

f:id:babcs2035:20190412231411p:plain