ACMP 592: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) (Новая страница: «== Ссылка на задачу == * [http://acmp.ru/?main=task&id_task=592 ACMP #592 — Небоскреб] == Похожие задачи == * Инт…») |
(нет различий)
|
Версия от 06:21, 6 января 2016
Ссылка на задачу
Похожие задачи
Комментарии
Присваиваем каждому отрезку уникальный id. Добавляем отрезки [0; 0] в каждом столбце, объединяем отрезки в соседних столбцах при помощи DSU.
Строим граф "кто на кого падает"; вес ребра (a-b) — минимальное расстояние от части a до части b. Количество ячеек, на которое упадёт каждая из частей, равна кратчайшему расстоянию от этой части до дна. Эти расстояния можно найти алгоритмом Дейкстры.