Помогите, пожалуйста, с задачей.
Задача: http://www.e-olimp.com/problems/3206
Что я попробовал: отсортировал ребра по весу. Иду по очереди и поддерживаю компоненты связаности. На каждом ребре (a, b, c) я смотрю на компоненты. Если a и b в одинаковых компонентах, то это ребро нам ничего не улучшит и я его пропускаю. Иначе, соединяю компоненты.
Потом для каждого запроса я смотрю, когда в первый раз a и b попали в одну компоненту. Очевидно, что ребро, которое соединило их компоненты и является самым тяжелым в самом легком пути от a к b. Это ясно, если вспомнить, что ребра были отсортированны по возврастанию в начале.
Реализация: Чтобы смотреть назад во времени на компоненты связанности, я храню все в персистентной структуре, где каждая операция за O(log2N). А для каждого запроса нахожу ребро, которое соединило компоненты a и b с помощью бинарного поиска за O(logN).
Суммарно выходит O(Qlog3N), что не влезает в ТЛ. Да и моя корявая реализация персистентного СНМ — очень кривая и занимает очень много памяти и не влазит в МЛ 64мб.
Мой код: там вообще кошмар на улице вязов. Реализовал первое, что смог. Этот код прошел все мелкие тесты (что подтверждает корректность идеи?). Ссылка.
Помогите решить задачу? Помогите научиться правильно писать персистентный СНМ?
Можно вообще без леса непересекающихся множеств. Просто будем поддерживать множества явно, а при выполнении операции union будем примердживать меньшее множество к большему. Кроме того, для каждого множества будем поддерживать запросы, такие, что одна вершина запроса лежит именно в этом множестве. При union-е кроме мерджа множеств также будем проверять, не оказались ли вершины из каких-то запросов в одном множестве, если оказались — мы нашли ответ на запрос.
UPD. Очевидно, такое решение работает за O(Q * log^2 N)
P.S. Про персистентный СНМ можешь почитать лекцию Копелиовича с харьковской зимней школы 2011 года.
Ну, я похоже перемудрил, как всегда. Я примерживал меньшее к большему, но так и не подумал, что можно на каждом шаге проверять, объединяем ли мы вершины из запроса. Как это делать, мне еще не понятно.
Все весьма просто. Запросы, одна вершина которых лежит в текущей компоненте, храним в set-е. При мердже двух компонент мы мерджим и запросы (если запрос есть в обоих set-ах, то мы на него отвечаем и выкидываем, а все остальные запросы добавляем в set результирующей компоненты). Т.к. для каждой вершины гарантируется, что она будет переброшена из компоненты в компоненту не более log N раз, то же самое гарантируется и для каждого запроса.
А вы сдавали такое решение? Моё упорно ловит ТЛ. Хоть я и на сетах пробовал, как вы расписали, и на векторах, чтоб лишнего логарифма не было...
Учитывая, что на е-олимпе сервер — полная параша, желания что-то туда пихать у меня совершенно нет...
Молодой человек, во-первых ведите себя как-то поприличней, а во-вторых — ну будьте двуличным. Ведь эти слова:
принадлежат именно Вам, и были сказаны не так давно — 2 года назад.
Вот такой вот я человек: одним мерзким поступком можно опустить себя в моих глазах ниже плинтуса.
Если Вы не понимаете, о чем я — перечитайте нашу переписку от 07.07.2011 (да, да, я очень злопамятный).
И вообще (насчет указания по поводу того, как мне себя вести): в подобных контекстах я называю вещи своими именами.
Эту задачу можно ведь совсем стандартно решить. Отсортировать ребра по опасности. С помощью обычного СМН склеить дерево по этому отсортированному списку. Далее запросы максимум на пути между вершинами в дереве, где ничего не меняется. Это просто двоичными подъемами делается.
что есть "обычный СМН"? обычный Система Множеств Непересекающихся?
Была тема про похожую задачу. Там описано решение за E log E + Q log Q
Спасибо, действительно такая же задача :).
Была идея начать с МСТ, но потом подумал, ведь МСТ найдет минимум по сумме. Но сейчас смотрю на свой же код и там я делаю крускала. Стыдно.
Как раз по сумме МСТ минимум не найдет:)
Да, видно годы мои не те.
Спасибо всем за комментарии. Стало понятно, что никакой персистентности тут и нет.
1