Your logic is perfect, the only flaw is that your travelling the entire path to find the taste. And in worst case this can be O(n). This will happen if the given H is sorted.
To speed up the queries you’ll have to use a BIT or a segment tree.
1 Like
I was not able to spot the bug in your implementation, also I’m not very fluent in python. However I ran some bash tests and your code fails for this test case below. You’re probably not handling the impossible case well. The rest seems to be right.
Test Case
10 1
873 597 892 20 227 716 594 235 875 875
310 407 169 441 366 721 317 819 562 491
2 10 4
Expected: -1
Output: 2090
2 Likes
I guess problem is with this statement:
if pre < h[i]:
taste += t[i]
pre = h[i]
if h[i] > h[b-1]:
taste = -1
break
Don’t you think if pre>h[b-1] you need to print -1 !!
And One more thing you will have solution if and only if you can reach b. If not able to reach then you should print -1. So add one more condition to check it.
2 Likes
pls suggest how to improve this Data Structures on Tree part…thanks in advance!
I’ll say just solve some standard problems on these data structures. Then you will start getting ideas/intuitions to solve such problems.
thank you for the suggestion
can I get the proper understandable solution to this question in python3, because I don’t know how to implement BIT and segmented tree here in this question, please
My language is C++, and I only know the very basics of python.
This submission might help you.
1 Like
thanks a lot for helping me @aneee004
I have looked at this code but due to lack of comments it is very hard to understand.
by the way thanks for helping me 
1 Like
The process of flattening the tree is called euler tour of the tree.
More information : On Euler tour trees - Codeforces
1 Like
Can someone please tell me on which test cases my solution is getting failed.
My sol:CodeChef: Practical coding for everyone
Mo’s Algorithm is an offline solution where as this question requires an online solution.
Hope you’ve got your answer.
thnx bro . we need this.