Прыжки между вселенными

Автор задачи: Даниил Орешников, разработчик: Константин Бац

Для решения этой задачи можно воспользоваться системой непересекающихся множеств (disjoint set union, dsu). Будем считать элементами внутри этой системы — миры, а множествами — наборы миров, взаимнодостижимых друг из друга при некотором текущем значении энергетического уровня $$$w_\mathrm{cur}$$$. Это напрямую следует из того, что если в какой-то момент мир становится достижимым, то после мы всегда сможем попасть в этот мир независимо от наших следующих действий, так как энергетический уровень часов не уменьшается. А тогда «достижимая область» всегда представляет из себя некоторый связный подграф исходного графа.

Тогда все, что надо делать — реализовывать «расширение» нашей достижимой области при увеличении энергетического уровня часов, а также увеличивать этот уровень при возможности посетить новые миры. Давайте внутри СНМ хранить множества взаимодостижимых по ребрам веса не больше $$$w_\mathrm{cur}$$$ миров. Помимо этого для каждого мира запомним его хранить характеристику $$$a_i$$$ и в множестве будем поддерживать сумму всех $$$a_i$$$ по элементам множества (достаточно хранить ее отдельным полем в представителе множества).

Заметим, что текущее значение энергетического уровня всегда равно сумме $$$a_i$$$ в множестве, в котором содержится мир с номером $$$s$$$, потому что в соответствующем множестве перед тем, как двигаться за его пределы, мы можем сначала посетить все его вершины и по максимуму увеличить энергетический уровень. Тогда $$$w_\mathrm{cur}$$$ можно найти в СНМ за время $$$\mathcal{O}(\alpha(n))$$$, что можно считать константой. Теперь посмотрим, как достижимых миров меняется:

  1. Отсортируем порталы по возрастанию $$$w_i$$$.
  2. Рассматривая очередной портал $$$(u, v)$$$, сравним его $$$w_i$$$ с текущим $$$w_\mathrm{cur}$$$, и если $$$w_i \le w_\mathrm{cur}$$$, то объединим множества, в которых содержатся миры $$$u$$$ и $$$v$$$. При этом не забываем обновить сумму $$$a_i$$$ в корне объединения.
  3. Если же $$$w_i > w_\mathrm{cur}$$$, то мы этим порталом воспользоваться не сможем, да и всеми последующими порталами тоже (так как они отсортированы по $$$w_i$$$) — в этот момент можно завершить алгоритм.

Таким образом, значение $$$w_\mathrm{cur}$$$ после рассмотрения всех порталов равно значению энергетического уровня часов, то есть ответу на задачу. В таком решении на обработку каждого портала потребуется $$$\mathcal{O}(\alpha(n))$$$ времени, поэтому время работы такого решения — $$$\mathcal{O}(n + m \alpha(n))$$$.