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