Сакурако та вкрадена легенда#412

Сакурако та вкрадена легенда (Розбір)

Автор:

Богдан Фейса

Підготовка задачі:

Богдан Фейса

Розбір:

Богдан Фейса

Блок : n, m \leq 80:

Ми обчислюємо всі сильно зв'язані компоненти (SCC) за \mathcal{O}(n^3) для кожного з моментів часу, використовуючи простий DFS. Після цього ми створюємо масив ans[i][j], 1 \leq i, j \leq n, який зберігає мінімальний момент часу, коли та знаходяться в одній SCC. Після цього ми відповідаємо на всі запитів за . Загальна часова складність: \mathcal{O}(n^3 \cdot m + q).

Блок : n, m \leq 10^3:

Ми обчислюємо всі SCC за \mathcal{O}(n + m) для кожного з моментів часу, використовуючи алгоритм Косараджу. Після цього ми створюємо масив ans[i][j], 1 \leq i, j \leq n, який зберігає мінімальний момент часу, коли та знаходяться в одній SCC. Після цього ми відповідаємо на всі запитів за . Загальна часова складність: \mathcal{O}((n + m) \cdot m + q).

Блок : q \leq 100:

Для кожного блоку ми використовуємо бінарний пошук для кожного запиту, в якому ми обчислюємо SCC разів за \mathcal{O}(n + m) часу.

Це призводить до загальної складності часу \mathcal{O}((n + m) \cdot q \cdot \log n).

Тепер ми вводимо офлайн інкрементальний алгоритми SCC, який працює за \mathcal{O}(m \log m) часу.

Давайте використаємо техніку розділення та володарювання на списку ребер. Ми також можемо думати про це як про розділення та володарювання по часовій лінії. Отже, припустимо, що у нас є функція rec(a, b, edges), де — початок інтервалу часу, — кінець (обидва включно), а edges — список ребер разом із часами, коли вони були додані. Ми починаємо процес з rec(0, m-1, everything).

Кожного разу, коли ми дивимося на середину інтервалу часу, ми обчислюємо s = \left\lfloor \frac{a + b}{2} \right\rfloor. Ми використовуємо стандартний офлайн алгоритм для обчислення SCC в графі, що складається лише з ребер з edges, які були додані в момент до . Ми хочемо розділити рекурсивно, не обчислюючи щось лишній раз.

Виявляється, що в моменти після всі SCC, які ми щойно обчислили, залишаться з'єднаними. Отже, ми можемо об'єднати цілі компоненти в окремі вершини і лише передати вправо ребра, що з'єднують різні компоненти. Ребра, що з'єднують різні компоненти, були непотрібними в минулому, тому ми передаємо решту вліво. Таким чином, кожне ребро з'являється один раз на кожному рівні рекурсії. Є \mathcal{O}(\log m) рівнів, і на кожному рівні загальна складність є лінійною. Отже, ми отримуємо складність \mathcal{O}(m \log m) (припускаючи обережну реалізацію без додаткових логарифмів).

Блок : Повне рішення, без тестів з t = 1:

Спочатку ми створюємо додаткові 2 \cdot q ребра і додаємо їх до графа. Це представляє запити. Потім ми використовуємо офлайн інкрементальний алгоритм SCC, щоб отримати інформацію про кожне ребро і чи його кінцеві точки знаходяться в одній SCC в будь-який момент часу. Після цього ми витягуємо відповіді з додаткових ребер, які ми додали.

Часова складність: \mathcal{O}((m + q) \log (m + q)).

Блок : Повне онлайн рішення:

Ми даємо вагу кожному ребру - час, коли його кінцеві точки знаходяться в одній SCC. (Вартість: \mathcal{O}(m \log m)). Після цього ми створюємо неорієнтовану зважену копію графа. Потім ми будуємо мінімальне остовне дерево (MST). (часова складність: \mathcal{O}(m \log m))

Нарешті, ми використовуємо бінарні підйоми (бінарні стрибки) + LCA (найнижчий спільний предок), щоб знайти максимальну вагу ребра на шляху від до в MST. (часова складність: \mathcal{O}(n \log n))

Загальна часова складність: \mathcal{O}(m \log m + m \log m + n \log n)