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:

https://drive.google.com/file/d/1ZZIUOhvEl-sldF9eY8HSjTMnusHsbGsM/view?usp=drivesdk

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

Does anyone have a solution that is lesser than O(n sqrt(400000)) for A? or is official solution also that .-.

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.

It doesn't work :(

Edit: I didn't read the code — this approach does work (it just uses too many queries in this instance)

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:

Edit: tidied up my code a little bit, https://pastebin.com/Fq3hDrGB

Does anyone know when are they releasing the results?

Friday, 21 August 2020 19:00 (UTC+7) is the closing ceremony

Is B solvable with MST?

Yes, but it is a bit simpler.

I think there is a solution that uses kruskal reconstruction tree to solve the problem

Is there any place to submit solutions yet?

https://tlx.toki.id/problems/apio-2020