Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

EmilConst's blog

By EmilConst, 4 weeks ago, ,

A month ago IZhO 2020 was held in Almaty, Kazakhstan. Thanks to Tima we can submit our solutions here. Here is editorial for problems day1 A, day1 B, day2 C. Please write solutions for other problems in comments.
Benq has published his codes for all problems here.

Observation
Final
Observation 1
Observation 2
Observation 3
Observation 4
Final

Read Tima's comment.

• +29

 » 4 weeks ago, # |   +13 That's great, thanks.
 » 3 days ago, # | ← Rev. 2 →   +29 Day 2 B (by request)Note: It's similar to C from here.Special case: $l=r$ Getting the # of vertices that are at most a distance $k$ away from a fixed vertex is a well-known problem. It can be done with centroid decomposition and a table that stores prefix sums at each level of the decomposition. General case:For each query, consider the centroid $c$ of the tree and the computer $i$ that determines its infection time (namely, the $l\le i\le r$ which maximizes $t_i+dist(c,v_i)$). This can be computed with a segment tree.Then the latest infection times for all computers $d$ outside the subtree of $c$ corresponding to $v_i$ will satisfy $infect_d=infect_c+dist(c,d)$. The number of such vertices that are infected within time $t$ can be computed as in the special case. Then we can recursively deal with the vertices inside the subtree corresponding to $v_i$ by considering the centroid of this subtree, and so on. Note that viruses that originate outside the subtree corresponding to $v_i$ must still be considered; this is what $extra$ is for in my solution.This can be done in $O(N\log N+Q\log^2N)$ if we process all updates before all queries.