Блог пользователя ErisSimp

Автор ErisSimp, история, 15 месяцев назад, По-английски

Can someone explain IOI 2011 RACE solution using CD?

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
15 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Like this problem: https://codeforces.net/problemset/problem/161/D but you save the shortest path with a path length i call it dp[i]. Assuming that you are considering centroid c, after going through a tree branch, you save the dp[i] as the shortest path of length i from c every time you move to a new branch, the result will update again as min(ans , dp[i]+dp[k-i]) with the condition dp[i]!=-1 && dp[k-i]!=-1. Because k is quite large, when you finish browsing 1 centroid, you will only update the dp you just reviewed. sorry my english is very bad My code for this problem: https://ideone.com/VOmd3A