But how that was a mistake ?
Since, I subtracted one when inserting weight, therefore, it should not matter in the end. right?
I have taken weight for city 1 to city 1, one because, I have checked if it was visited or not by checking the value of W array if it is 0 or not
Yes, exactly, when I was debugging it, it seemed correct, but I just experimented with it.
Also, I defined int as a long long int for safety reasons.
I am also wandering why your code is incorrect, if I just wrote it in another way.
Ohh, issue was overflow
Yes, by looking at the constraints i defined int as long long int
Your WA code without long long int - Click Here
Yeah, got it, issue is overflow somewhere
You can check for overflow using the technique described here
Overflow is here mate,
int wt=q.front().second;
q.front().second is long long.
ll wt=q.front().second;
Here overflow was occurring Line 76
Exactly
Can’t use advantages of these
I use CC IDE
try:
def visi(a,b):
for i in a:
if b[i]==0:
return 1
return 0
def dfs(b,c,n,m,sum,v,ans):
if visi(b[n],v)==0:
ans.append(sum)
return
for i in b[n]:
if v[i]==0:
v[i]=1
dfs(b,c,i,m+1,sum+m*c[n][i],v,ans)
def solve():
ans=[]
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=[[] for i in range(n)]
c=[[0]*n for i in range(n)]
for _ in range(n-1):
x,y,z=map(int,input().split())
b[x-1].append(y-1)
b[y-1].append(x-1)
c[x-1][y-1]=z
c[y-1][x-1]=z
vis=[0]*n
vis[0]=1
dfs(b,c,0,1,0,vis,ans)
ans.sort()
a.sort()
i=0
j=0
count=0
while i<len(ans) and j<len(a):
if a[j]<ans[i]:
j+=1
continue
else:
j+=1
i+=1
count+=1
print(count)
for _ in range(int(input())):
ans=[]
solve()
except:
pass
what’s wrong here it is giving tle
It seems my code is correct - Click Here
But I am getting WA in it, I have also checked the corner case (didn’t consider 1 as the special city).
I ran a BFS and calculated the total energy to reach every node from node 1 and stored it, then took all leaf nodes energies and greedily checked with energies available.
Can anyone point out the mistake. It’ll be really helpful.
My submission : CodeChef: Practical coding for everyone
Can anyone help me with my WA?
I’ve done almost the same except for the final part of the problem. I used DFS to calculate the depths and energies.
Can this problem be solved using Dijkstra algorithm? I mean at first I have to calculated the minimum cost from the capital city to all cities using Dijlsktra… And then find the number of special city then the answer using multiset…
In theory yes, but we use a special characteristic of trees. We can simply do the dfs traversal of a graph because there’s only a single path between every two vertices.
As for the multiset, every leaf occurs only once so you can get away with a simple set or just an array sorted in increasing order and greedily match pilgrims with lowest energy to leaves of smallest distance. 
I had a doubt. Feel free and please do reply.
This is my soln. I got WA and I didn’t have any Run time Errors.
I used dfs in the question and didn’t use bool visited array. Is it one of the correct way to solve? (Note while inserting I inserted unidirectional directional link betn cities).
If possible can someone tell me what was wrong with my code ?
You should add bidirectional edges in your graph, since input can be given as:
1 3
2 3
In your case you won’t consider 3 - 2 as an edge, meaning you’ll consider 3 as a leaf rather than 2.
This introduces a new issue in your code which is dfs without visited array. You still don’t need visited array, but need a way to tell whether the vertex u is parent of v. This can be solved by introducing parent variable in the dfs defintion.
Also in your later while loop you’ll need a way to break out of the loop once j reaches its maximum value, not only i, because there could be fewer leaves than pilgrims.
I believe this should fix all the issues.
Hey anyone here please check my code which getting WA but i think my approach is right and also i considered all the corner cases CodeChef: Practical coding for everyone
hey aadiupadhyay please check my code which getting WA but i think my approach is right and also i considered all the corner cases Solution: 45071706 | CodeChef