Авторы задачи: Константин Бац, Мария Жогова и Даниил Орешников, разработчик: Мария Жогова
Рассмотрим путь раствора с отдельной точки халата, на которую он был нанесён.
По условию, длина этого пути — расстояние от этой вершины до ближайшей дырки. Поскольку вес любого ребра в нашем графе равен единице, то для поиска кратчайшего расстояния до любой дырки в таком графе можно использовать поиск в ширину (bfs). Запустим множественный bfs из всех дырок в халате, чтобы узнать расстояние от них до всех капель. Если бы нельзя было добавить новую дырку в халате, то ответом был бы максимум из этих расстояний.
Теперь попробуем улучшить ответ, добавив новую дырку. Сделаем бинпоиск по ответу. Очевидно, что если можно достичь ответа $$$\leqslant d$$$, то можно и достичь ответа $$$\leqslant d + 1$$$. Осталось научиться проверять, что можно достичь ответа $$$\leqslant d$$$.
Для тех капель, для которых расстояние до исходных дырок не больше $$$d$$$, больше ничего делать не надо. Для оставшихся капель достаточно найти вершину на расстоянии не больше $$$d$$$ до каждой из них, после чего сделать в ней дырку. Для этого сделаем bfs из каждой такой капли по отдельности и найдем для каждой оставшейся вершины графа максимальное из кратчайших расстояний до капель. Если нашлась вершина на расстоянии не больше $$$d$$$ от каждой из капель, то в бинпоиске двигаем правую границу, иначе левую. Поскольку гарантируется, что капель не больше $$$s \leqslant 100$$$, время работы такого решения будет равно $$$\mathcal{O}(\log n \cdot (n + m) \cdot s)$$$, что проходит по времени.