Is my alternate approach to USACO 2012 Gold December Contest: "Running Away From the Barn" valid?

Правка en1, от vamaddur, 2017-07-04 23:20:41

Problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=213

For whatever reason, implementing any of the three official editorial solutions is not working out for me, so I am changing tact.

My idea is to store the depths relative to the root for each node, run a DFS and BIT similar to what I used in this problem, add/subtract values to/from the BIT according to a sliding window (e.g. when L = 3 and a node with depth 5 is at the bottom of the sliding window, nodes with depth of at most 8 are at the top), and query all nodes in the window that are ancestors of the node in question.

I would appreciate comments on my method.

Please help, and thanks in advance!

Теги usaco, bit/fenwick tree, preorder traversal

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский vamaddur 2017-07-05 16:04:44 1916
en1 Английский vamaddur 2017-07-04 23:20:41 822 Initial revision (published)