Editorial for WOSS Dual Olympiad 2023 S3: Flying

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: 404

To solve the first subtask, let $dp[a][b]$ ~dp[a][b]~ be either 0 or 1, representing if we can reach node $a$ ~a~ with a path of exactly $b$ ~b~ in length. Use BFS to calculate all the states, then answer queries in constant time. Time complexity: $\mathcal{O}(Nc_i+Q)$ ~\mathcal{O}(Nc_i+Q)~.

Let $k$ ~k~ be the length of any edge attached to node 1. If we can reach node $a$ ~a~ with a path of length exactly $b$ ~b~, we can also reach node $a$ ~a~ with paths of lengths ( $b+2k$ ~b+2k~), ( $b+4k$ ~b+4k~), ( $b+2nk$ ~b+2nk~).

Thus, let $dp[a][b]$ ~dp[a][b]~ be the minimum distance required to reach node $a$ ~a~ such that $dp[a][b] \mathop{\%} 2k = b$ ~dp[a][b] \mathop{\%} 2k = b~. This can be computed using Dijkstra. Then for each query ( $q_i$ ~q_i~, $c_i$ ~c_i~), check if $dp[q_i][c_i \mathop{\%} 2k] \leq c_i$ ~dp[q_i][c_i \mathop{\%} 2k] \leq c_i~. If the statement is false then it is obviously not possible. If it is true then $c_i$ ~c_i~ can be written as $dp[q_i][c_i \mathop{\%} 2k] + 2nk$ ~dp[q_i][c_i \mathop{\%} 2k] + 2nk~, so it is possible. Time complexity: $\mathcal O((Nl_i)\log(Nl_i)+Q)$ ~\mathcal O((Nl_i)\log(Nl_i)+Q)~.

Comments

1

relx commented on Jan. 19, 2024, 2:27 a.m. ← edited →

I don't understand why the edge ( $k$ ~k~) has to be directly attached to 1

4

thomas_li commented on Jan. 19, 2024, 5:05 p.m.

because otherwise you'll have to traverse some other edges to reach the edge k, where as if it's attached to 1, you can add 2k freely.

3

relx commented on Jan. 20, 2024, 9:09 p.m.

thx but what if the edge you have to traverse twice is not directly connected to node 1 how would that work?