Editorial for DMOPC '21 Contest 6 P4 - Colourful Paths - Olympiads Online Judge

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.

Author: Riolku

We always need exactly two colours.

For the first subtask, it is impossible if $C$ $C$ and $D$ $D$ are adjacent or $C$ $C$ and $D$ $D$ are on the $AB$ $A B$ path.

For the second subtask, it is impossible if $C$ $C$ and $D$ $D$ are adjacent or $C$ $C$ and $D$ $D$ are on all $AB$ $A B$ paths. Run a BFS, storing the node as well as an extra value indicating which of $C$ $C$ and $D$ $D$ have been visited. This guarantees finding a colouring with a shortest path. To colour, if $C$ $C$ is on the optimal path, colour all edges adjacent to $D$ $D$ differently, similarly if $D$ $D$ is on the optimal path. If neither are, choose one at random to block off.

Comments

There are no comments at the moment.