Can someone please help me figuring out why I am getting a Run Time error (Segmentation Fault) in my code.
Problem.
My solution.
BRIEFING MY SOLUTION:
-
I have ran a dfs to find the depth and parent of a node. There are two arrays ‘Increasing’ and ‘Decreasing’. Increasing stores the node(only consisting of ancestors) till which the values are strictly increasing. Array decreasing does the similar thing, in which values decrease.
-
After that, I make a sparse table, for computing LCA(x, y) in (O(log n)).
-
While processing the queries, I find the LCA of the two nodes, and then check the conditions which will result in the answer 1 and 0.
1 Like
Thank you for the awesomely formatted question (pleases the eyes, refreshes the mind, etc.)!
Some mistakes I see:
- On lines 108 and 116, shouldn’t it be
depth[x] and depth[y] respectively?
- Why does it have to be true that the path is increasing from x and decreasing towards y? For example, if the entire path is monotonic and ends at x or y. Also, wouldn’t it be that it’s increasing from x and increasing from y (which is an equivalent statement, but you seem to be handling it differently)?
- Your code will probably TLE because of
ini
- I think your RE is on line 138, you take the value of
Decreasing at an array value, but A_i \leq 10^9
2 Likes
Thank you for finding my mistakes. I would have spent hours on debugging the errors.
Why does it have to be true that the path is increasing from x and decreasing towards y?
I guess Increasing[x] and Decreasing[y] handle it. Because from x to ancestor the path is increasing, and if depth[Decreasing[y]] <= Depth[ancestor], this means that the path is decreasing from y to ancestor, thus when considered in the opposite direction, it is increasing from ancestor to y, thus the whole length is increasing from x to y.
And for the other way, after Decreasing[x] and Increasing[y] should handle it. (I got confused and wrote Decreasing[y] by mistake, in the code). I guess that is why I am getting a WA, after you helped me with the bug for RE.