Editorial for Another Contest 9 Problem 3 - Sun & Moon
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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Note that we can loop back on a given edge to stay at the same vertex with a delay of either 2, 4, or 6 years. Therefore, we can track for each residue modulo 12 (the LCM of 2, 4, and 6) the minimum number of years needed to get to that vertex, and then we can always revisit that vertex any multiple of 12 years later. This problem then reduces to running a shortest path algorithm on the induced graph of vertex and residue modulo 12.
Comments