Editorial for DMOPC '21 Contest 6 P4 - Colourful Paths
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.
Author:
We always need exactly two colours.
For the first subtask, it is impossible if and
are adjacent or
and
are on the
path.
For the second subtask, it is impossible if and
are adjacent or
and
are on all
paths. Run a BFS, storing the node as well as an extra value indicating which of
and
have been visited. This guarantees finding a colouring with a shortest path. To colour, if
is on the optimal path, colour all edges adjacent to
differently, similarly if
is on the optimal path. If neither are, choose one at random to block off.
Comments