Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### dvdg6566's blog

By dvdg6566, history, 3 years ago,

Hello codeforces!

With the conclusion of APIO 2020, we have compiled an unofficial editorial for all 3 problems.

Credits to bensonlzl oolimry for helping with the compilation. The editorial can be found at the following link:

Special thanks to APIO committee for an interesting problemset this year!

• +93

 » 3 years ago, # |   +34 Does anyone have a solution that is lesser than O(n sqrt(400000)) for A? or is official solution also that .-.
 » 3 years ago, # | ← Rev. 5 →   +18 Oops, I wasn't able to pass this approach for C ... I think this should work (for $N\le 500$) but I'm not sure why this takes care of the "edge" cases.EDIT: Nvm, I see why it works.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +18 It doesn't work :(Edit: I didn't read the code — this approach does work (it just uses too many queries in this instance)
•  » » 3 years ago, # ^ | ← Rev. 2 →   +28 For the edge case, here's what I did.Terminology: Let the centroid be R, the subtrees be X,Y,Z. wlog let X be the biggest subtree. This edge case occurs is at the point where SZ(X) = SZ(Y) + SZ(Z) + 1, we are currently in subtree Y, where ht(X) < ht(Y) < ht(Z). In this case, we will jump from Y, then to X, then to Z. However, we cannot do this as ht(Z) + ht(X) > ht(Y) + ht(X). To resolve this, we make an additional jump from Y to Z. This is my implementaton: if(t.s!=MAJ && t.f!=-1 && SZ(res) && pd[res.back()] < t.f){ res.pb(t.s); V[belg[t.s]].pop_back(); blk=-1; } Edit: tidied up my code a little bit, https://pastebin.com/Fq3hDrGB
 » 3 years ago, # |   +8 Does anyone know when are they releasing the results?
•  » » 3 years ago, # ^ |   +46 Friday, 21 August 2020 19:00 (UTC+7) is the closing ceremony
 » 3 years ago, # |   0 Is B solvable with MST?
•  » » 3 years ago, # ^ |   +1 Yes, but it is a bit simpler.
•  » » 3 years ago, # ^ |   +1 I think there is a solution that uses kruskal reconstruction tree to solve the problem
 » 3 years ago, # |   0 Is there any place to submit solutions yet?
•  » » 3 years ago, # ^ |   +8