Can anyone please help me in telling where am I getting wrong in my LCA code(using Sparse Matrix)
due to which I am getting TLE on subtask 1 itself!..Its the first time I am trying this approach so I think I am having some implementation issues, but I am unable to figure them out!
Could you please help me find this bug ? I intend to solve this problem to learn the mo’s algorithm in a better way . Pigeon-hole’s principle was definitely a show winner . https://www.codechef.com/viewsolution/33527299
Pigeonhole is a very basic thing in maths/cp, though it didn’t click me during the contest (-_-;). Nice editorial. Nice problem. But what if A_i is much greater? Can anyone tag such problem or editorial right here?
The code in java does not work without the fast reader. I usually use fastreader but i forgot to use this time around…can anyone tell me from where can we detect that the i/o is causing the problem?
Can any1 tell whats wrong with my code? I use simple DFS and store path in a vector. Then I calculate the minimum among them . It should pass Subtask 1 .But its giving WA https://www.codechef.com/viewsolution/33513447
The first number in the pair is the depth of the vertex in the dfs order, while the second one is its id (not that each vertex appears multiple times in the order).
@witcher98 in worst case your solved function would run for O(N).
The worst case for your code is when the nodes of the tree from a chain and you have to go from the leaf node to the root. Thus making your time consumption O(Q.N)
@ameybhavsar a single dfs run takes O(N). So running DFS for each query would lead the time complexity to O(Q*N). That’s where your code failed.
Tip: In-case the nodes and paths of tree are static try building an intuition to solve problem by finding LCA, most of the time it really helps during short contests.
why i am getting tle on 2 subtask.My code is same as setter’s code only the dfs function is implemented a bit differently.Can anyone tell me.Thanks in advance.