CENS20F - Editorial

editorial
, ,
35

I am getting WA for the below solution … i dont know whats wrong. please help!
https://www.codechef.com/viewsolution/37019870

36

Can someone explain how a star-shaped tree would result in a TLE?

38

Can anyone please tell me where my code fails… I cannot find it. I’m getting TLE on submission
https://www.codechef.com/viewsolution/37027990

39

https://www.codechef.com/viewsolution/37029733
My solution is almost same but I keep getting the please help

41

for each query,i made a dfs and added even distnce of subtree values to vertex.
As it is mentioned sum of all N and Q over all test cases doen’t exceed 200000 ,its no where near to get a TLE,but i did get TLE :grimacing:,can anyone look into my code and say what’s wrong?
https://www.codechef.com/viewsolution/37033454

42

Not Accepted, WA… Please someone provide any test case which it cannot pass

43

@aert Do you have more test cases? It worked for all you’ve given above

44

1
3 1
1 1 1
3 2
2 1
1
You are creating a kind of directed tree so it is unable to go further from node 1.
Your output - 1 1 1
Correct output - 2 1 0

1 Like
45

https://www.codechef.com/viewsolution/37040905
Thanks man, Really confused by the question statement bc just started trees.

46

Why we simply can’t use BFS in directed graph and maintain distance array and update the A[i] values at the even distanced node ?? What’s wrong in this approach can anyone help me i am new to the graph and not able to figure out the mistake ,…

47

why my solution is giving WA i hv used bfs to calculate distances of all nodes then using dfs i calculated in and out time to check wether 2 nodes lie on same path or not then i run a loop checking all even distances nodes and same path nodes then shifting them
https://www.codechef.com/viewsolution/37056580

48

you can check my code I have also done this ques with BFS CodeChef: Practical coding for everyone

49

https://www.codechef.com/viewsolution/37119800
Could you tell me on which test case is my solution failing?
I have tried both of the test cases, that you have commented in this thread, and in both my code outputs the correct answer. Also, the logic seems to be what I implemented. Could you please check @ae

50

Same problem as this

1 Like
51

@aert My bad, I thought the inputs would directly give me a directed tree. I just corrected that. And, it passes for the above test case, yet it still cannot pass the submission. Could you please provide a test case for where it fails

52

@aert , could you please tell me where I am going wrong
My submission - CodeChef: Practical coding for everyone
1
3 1
1 1 1
3 2
2 1
1
1

53

It has been a few hours now!
@aert , could you help me out?

54

I am not sure how you are keeping track of the visited nodes using the map but here is a case on which your solution fails
1
4 2
6 2 7 3
1 2
2 3
3 4
1
2
Node 3 is being marked as visited so the query from node 2 is unable to reach node 4.

Another potential problem is that you are not marking the source node as visited. If the input is star shaped, for each query you will end up visiting all its neighbours.

1 Like
55

Can you kindly tell me sir, what is your complexity per query? I feel it is O(n*q) which amounts to 10^10 operations that should not pass in a 1.5 s time limit…
If you can kindly address this doubt or anyone else out here…
thanks in advance

56

could you please tell how you are generating so many test cases, just by thinking or you have used some kind of generators or something?