Anuar's blog

By Anuar, 6 years ago, In Russian,

Недавно узнал про такую интересную структуру данных как Heavy-Light декомпозицию(Статья в вики). Решил задачу на тимусе, но хотелось что-то посложнее... Поэтому специально зарегистрировался на SPOJ.com нашел задачу QTREE3 закодил и отправил. Но вот в чем проблема: она не проходит ни одни тесты. Решил погуглить но ничего дельного не нашел. Я прошу подправить мою идею если она оказалась не совсем правильной.

Вот в чем она состоит:

  1. Сделать HLD
  2. Обновлять цвета вершин с помощью дерева отрезков
  3. На каждом пути который мне встречается брать самую последнюю черную вершину

UPD: Все я наконец понял свою ошибку. Почему то если я делаю дерево отрезков для каждого пути то оно проходит) Окончательный код.

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it