ErisSimp's blog

By ErisSimp, history, 15 months ago, In English

Can someone explain IOI 2011 RACE solution using CD?

  • Vote: I like it
  • +6
  • Vote: I do not like it

| Write comment?
»
15 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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