ACMP 592
(перенаправлено с «Интернет-олимпиада 24.12.2005, усложнённый уровень, G»)
Перейти к навигации
Перейти к поиску
Ссылка на задачу
Похожие задачи
Комментарии
Присваиваем каждому отрезку уникальный id. Добавляем отрезки [0; 0] в каждом столбце, объединяем отрезки в соседних столбцах при помощи DSU.
Строим граф "кто на кого падает"; вес ребра (a-b) — минимальное расстояние от части a до части b. Количество ячеек, на которое упадёт каждая из частей, равно кратчайшему расстоянию от этой части до дна. Эти расстояния можно найти алгоритмом Дейкстры.