Блог пользователя mkagenius

Happy New Year: Problem F video tutorial (little tad abstract)
Автор mkagenius, 11 лет назад, По-английски

379F - New Year Tree

Video Link

I wanted to go into details — but it would have been a full 30 minutes. Any suggestion/query is welcome.

  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I don't think your solution can pass the system test. I think it will be TLE. In the worst case, updating the nodes' information can be O(n); So it's O(q*n)? Did I misunderstand? :D

→ Ответить
  • »
    »
    11 лет назад, # ^ |
    ← Rev. 7   Проголосовать: нравится 0 Проголосовать: не нравится

    updating will take O(log(n)) per query. Something like:

    cin >> current_query_node;

new_node_first = current_query_node + 1;
new_node_second = new_node_first+1;
P[new_node_first][0] = P[new_node_second][0] = current_query_node;
for (j = 1; 1 << j < N; j++)
                 P[new_node_first][j] = P[new_node_second][j] = P[P[new_node_first][j - 1]][j - 1];

    So, we are building the data structure for LCA incrementally after each query.

    For more info check out "Another easy solution in <O(N logN, O(logN)>" section on TC

    → Ответить