Последняя лекция

  1. [20 минут] Кучи. Окончание.
    1. Учим фибоначчиеву работать за O(logC), Дейкстра сразу работает за O(m + nlogC)
    2. Двухуровневый Radix Heap за O(sqrt(logC))
  2. [20 минут] Центроид декомпозиция
    1. Структура. Построение за O(nlogn)
    2. Предподсчёт за O(nlogn) и ответ за O(logn) на запрос "аддитивная функция на пути"
    3. Упражнение: запрос − количество вершин на расстоянии k от данной.
      4. --- Перерыв ---
  3. [20 минут] Задача на жадность
    1. Дано дерево зависимостей, нужно выполнить задачи, минимизируя суммарный штраф.
    2. Решение без зависимостей: сортировка по частному