Editorial for COCI '15 Contest 3 #3 Molekule
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.
The key observation in this task is to notice that we can always construct the solution so that the longest path an impulse has to travel is . Since the graph of molecules is a tree, we can color the molecules in two colors (e.g. black and white) using the DFS algorithm so that there are no two molecules of the same color that are connected with a covalent bond. Now we must direct each covalent bond so that it points from the white molecule to the black one. It is clear that a path longer than does not exist in the newly created graph.
Notice that the claim can be generalized to any bipartite graph.
Comments