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 and D are adjacent or C and D are on the AB path.

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


Comments

There are no comments at the moment.