AlexanderBolshakov's blog

By AlexanderBolshakov, 12 years ago, In Russian

Во время решения задачи С со 119 раунда я столкнулся с невозможностью запихать в ТЛ решение на Java, де-факто аналогичное авторскому: бинпоиск + БФС с СНМом. В чем причина столь маленького ТЛа? Команда Codeforces не переписала авторское решение на Java? Или я не прав? В любом случае, я считаю, что это ненормально, когда на жабе заходит решение только у 14 человек (включая дорешивание).

P.S. Решение через построение "диаграммы Вороного" и последующий запуск алгоритма Крускала у меня зашло за 840мс.

UPD. Под выражением "построение "диаграммы Вороного"" я подразумевал разбиение вершин на множества в соответствии с тем, какой из волонтеров (или точка назначения) находится ближе всех, делал я это БФСом. Можно сказать, что я неявно построил граф с этими множествами в качестве вершин, и объединял их до тех пор, пока s и t не окажутся в одном множестве (как в алгоритме Крускала).