@virtuality Although you are keeping track of repeated node values, you should also keep track of the number of nodes (call that len) in the path.
Then, keep incrementing len in the loop on line 49, whenever you add a node to the path.
After line 58, inside the loop, check whether len > 100, if yes then you can print 0 as the answer due to pigeonhole principle.
Keep coding
No need for that because when len becomes > 100, automatically by pigeon hole principle Iāll get a repeated value which my code will detect.
I found the problem. The problem was with unordered_map and unordered_set. I had this problem once before, so thatās why I was able to guess it this time. It seems these STL hash sets donāt scale efficiently. So by reserving the capacity in the beginning itself, it could perform lookups in O(1) time. Here is the modified code: CodeChef: Practical coding for everyone . Added lines 109-111.
May be the distance between nodes should be greater than 100 ? or might not be clear vector after another test case.
https://www.codechef.com/viewsolution/33604155
i followed the above approach ā¦i am not able to even get 30pts?
can u please tell me my mistake
I would like to know, instead of Binary Lifting,what other technique can we use to find LCA in logN time??Kindly suggestā¦
[[quote=āsayan_1999, post:132, topic:67092, full:trueā]
I would like to know, instead of Binary Lifting,what other technique can we use to find LCA in logN time??Kindly suggestā¦
[/quote]
afsdf
first verify yourself then post such things
I found no such thing on the internet.Kindly say the full nameā¦
https://www.codechef.com/viewsolution/34001021
I cannāt find a test-case for which it fails.
Can anyone give me a test case or fix my code?
@vivek_1998299 can you help me?
Thanks!
// path length
long long path_length = level[a] + level[b] - level[lca];
Just replace this with this .
Actually the distance between two nodes (a,b) = level[a]+level[b]-2*level[lca]
.
Here is the link to correct solution of your code ā Your code
Thanks for pointing that out. How did I miss this
Paramara, Pratishtha, Anushashan.
Yeh hai, coding ke teen stambh.
You must have missed one of it.
Actually it is level[a]+level[b]-2*level[lca]-1
. Your code passed because I chose a larger value for path_legth(120) instead of 100.
Edit: Actually the test-cases are weak. Thereās no case for path_length = 101
The below code getting RE (NZEC) error can anybody please help me
cook your dish here
n=int(input())
while(n>0):
N,Q=map(int,input().split())
L=list(map(int,input().split()))
P=[]
C=[]
H=[0]*(N+1)
for i in range(N-1):
u,v=map(int,input().split())
P.append(u)
C.append(v)
H[v]=H[u]+1
#printĀ§
#printĀ©
#print(H)
#print(L)
while(Q>0):
u,v=map(int,input().split())
Sl=[]
while(len(Sl)<100 and u!=v):
if(H[u]>H[v]):
Sl.append(L[u-1])
u=P[C.index(u)]
elif(H[u]<=H[v]):
Sl.append(L[v-1])
v=P[C.index(v)]
else:
Sl.append(L[u-1])
u=P[C.index(u)]
Sl.append(L[v-1])
v=P[C.index(v)]
Sl.append(L[u-1])
if(len(Sl)>=100):
print(0)
Q=Q-1
continue
Sl.sort()
min=100
for i in range(len(Sl)-1):
if(min>Sl[i+1]-Sl[i]):
min=Sl[i+1]-Sl[i]
if(min==0):
break
print(min)
Q=Q-1
n=n-1