Помогите, пожалуйста, с задачей.
Задача: 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мб.
Мой код: там вообще кошмар на улице вязов. Реализовал первое, что смог. Этот код прошел все мелкие тесты (что подтверждает корректность идеи?). Ссылка.
Помогите решить задачу? Помогите научиться правильно писать персистентный СНМ?