PROBLEM LINK:
SPCWAR The Space War IUPC Plinth 2020
Author: Kabeer27
Editorialist: Kabeer Seth
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Connected Components, BFS, Diameter of Tree
PROBLEM:
Optimally place source points of information in each of the connected components to obtain minimum time.
EXPLANATION:
Find all the connected components and then in each connected component place your source node as the center of the diameter, the time taken to spread will be diameter/2 for each connected component, now just compute the maximum of all the diameter/2.
The center of the diameter will be the most optimal point as the longest possible path in any connected component will be the diameter, if we choose any other points it will take more than diameter/2 time.
AUTHOR’S SOLUTION:
Author’s solution can be found here .