Настройки поиска (Страница 2 из 15)

Ну суффиксный автомат ацикличен, поэтому при подсчёте path_exists_i для текущего состояния мы можем считать, что для всех состояний, в которые есть рёбра из текущего состояния, всё уже посчитано. Поэтому мы можем просто брать ответы для них, а глубже уже не заходить.

Ещё раз, мы склеиваем три строки через три разделителя, строим по получившейся строке суффиксный автомат. Далее для каждого состояния автомата обходом в глубину (или динамикой с меморизацией, как угодно называть) мы находим три булевских величины: path_exists_1, path_exists_2, path_exists_3, где path_exists_i означает "из текущей вершины есть путь, заканчивающийся символом, равным разделителю номер i, и при этом не содержащий других разделителей".

После этого ответом на задачу будет просто состояние v, для которого все три величины равны true (точнее, искомая подстрока будет длиннейшим путём из истока в это состояние v).

Исправил.

Спасибо всем за то, что оперативно писали о проблемах.

Вероятно, заражение произошло так: некий вирус попал ко мне на домашнюю машину, украл FTP-пароль и автоматически заразил все JavaScript-скрипты на сайте.

Кажется, что иными словами всё это доказательство можно записать так.
Либо путь P содержит те же рёбра, что существовали и на предыдущей фазе, поэтому короче он стать не мог.
Либо путь P содержит какие-то новые рёбра, которые не существовали в остаточной сети на предыдущей фазе (однако учтём, что ребро могло появиться в остаточной сети только в результате пропускания потока вдоль этого ребра в обратном направлении). Рассмотрим первое "новое" ребро (u,w) из пути P; тогда, раз по нему пропустили поток на предыдущей фазе, то level_{i-1}[ u ] > level_{i-1}[ w ]; для вершины u мы можем использовать первую часть доказательства леммы, т.е. level_{i+1}[ u ] >= level_i[ u ]; наконец, в пути P расстояние до вершины w на единицу больше расстояния до u, поэтому level_{i+1}[ w ] > level_{i+1}[ u ]; собирая всё вместе, получаем level_{i+1}[ w ] > level_i[ w ]. Проделывая это же для всех остальных "новых" рёбер пути P, получим в итоге требуемое неравенство для вершины v.

Я позже вернусь к этой статье и попробую улучшить непонятные места. Будет хорошо, если вы отпишетесь, что ещё было описано в статье не слишком удачно.

Вообще это называется компонентами вершинной двусвязности. Неформально - каждая такая компонента - это набор рёбер, отделённых от остальных компонент точками артикуляции. Формально - каждая компонента - это такой набор рёбер, что для любой пары рёбер из этого набора их концы можно соединить вершинно непересекающимися путями.

Искать их можно в том же обходе в глубину, который применяется для поиска точек артикуляции. Надо ввести глобальный стек для рёбер, и при каждом проходе по ребру (в обходе в глубину) добавлять его в этот стек (только не надо добавлять одно и то же ребро дважды: из двух вариантов ориентации надо добавлять только первый), а при обнаружении точки сочленения ("if (fup[to] >= tin[v])") доставать из стека все рёбра вплоть до ребра (v,to) - эти рёбра образуют очередную компоненту вершинной двусвязности. После обхода в глубину из рёбер, оставшихся в стеке, также следует образовать отдельную компоненту.

Да уж, позапихивать пришлось так ещё

Вот мой код: http://pastebin.com/Gr2EAHwV, даёт 1.40 сек.

Из хаков:

• Не хранить в дереве уже отсортированные вершины, т.е. на i-ом шаге в дереве хранятся только n-i+1 вершин (у теории - улучшает примерно в два раза).

• Ручной ввод-вывод, вместо обычных scanf/printf: оперировать только с gets/puts (без этого у меня тоже не проходило, так что достаточно важно).

• А вот при подсчёте номера вершины и раскручивании предков, как оказалось, вполне можно использовать рекурсию вместо хранения предков в массиве: в данном случае рекурсия почти не сказывается на времени работы.

Интересно отметить, что на SPOJ'е суммарное N по всем тестам около 200 тыс., т.к. получается примерно 0.7 сек на 100 тыс. сложных операций с декартовым деревом: вот такое оно медленное.

Забавно, что именно сегодня я тоже сдавал эту задачу на тренировке
Не знаю, как там на spoj, но у меня проблем с TL не было. Выложи куда-нибудь код, может, там есть какой-нибудь косяк.

Отсортируем рёбра графа, и будем идти по ним в порядке от самых дорогих к самым дешёвым. Идея такая: на текущем шаге мы рассматриваем только рёбра с весом >= текущего, и мы смотрим, какие компоненты связности получаются из этих рёбер, и внутри каждой такой компоненты связности ответ между всеми парами вершин можно присвоить весу текущего ребра (только, понятно, для тех пар вершин, для которых ответ уже был найден ранее, обновлять его не надо).

Чтобы написать это за нормальную асимптотику, нужно явно хранить для каждой вершины номер её компоненты связности, и при рассмотрении текущего ребра смотреть: если оно соединяет вершины разных компонент, то эти две компоненты сливаются в одну, а ответ обновляется для всех пар вершин вида "(вершина_из_первой_компоненты;вершина_из_второй_компоненты)".

Итого будет решение за O(n^2) плюс предварительная сортировка за O(n^2 log n).

Надо найти такую вершину v, у которой st[v].len максимально, и при этом из этой вершины есть путь, содержащий @ (но не #$), есть путь, содержащий # (но не @$), и есть путь, содержащий, $ (но не @#).

Исправлено, спасибо.

Да, вы правы, массив used совсем не обязателен, достаточно лишь сравнения с текущим предком - p.
Исправил код.