ADA and Orange Tree SPOJ (LCA)

Правка en1, от SLIMSHADYNICK, 2020-03-13 22:19:21

I tried solving the problem the following way: 1) Using dfs I maintained the euler tour of the graph,height(or depth) of nodes,along with first and last occurence of index in euler tour. 2) Built a segment tree to give the minimum depth node in an interval along with its index. 3) Built another segment tree to give the number of different colors within an interval in the euler tour array.(I used Bitsets in java here). 4) for each query I calculate first the lca of the given nodes, call it X,using first segment tree. 5) then using first and last pos of X in the euler tour I calculate the number of different colors in this interval,using second segment tree.

But unfortunately I have been getting TLE at 15th test case. I tried optimising it a lot but its not working. Any help would be appreciated!

Теги lca/rmq, #spoj, #graph theory

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский SLIMSHADYNICK 2020-03-14 22:17:13 49 Tiny change: 'reciated:)' -> 'reciated:)\n\nUPDATE: GOT accepted with c++ the same logic!'
en2 Английский SLIMSHADYNICK 2020-03-14 03:53:53 432
en1 Английский SLIMSHADYNICK 2020-03-13 22:19:21 860 Initial revision (published)