INTRPATH - EDITORIAL

Good point about “\n” instead of endl. This change makes it AC as well. And even a bit faster than printf/scanf (2.23 s vs 2.47s).
https://www.codechef.com/viewsolution/24862468

1 Like

I think it’s endl which is causing TLE ??

@aman_robotics or any java bros
would u give us some tips on java
for INTRAPATH
my java soln gave tle while cpp passed
https://www.codechef.com/viewsolution/24808106

complexity is same as mentioned in official editorial i.e . logn for queries and nlogn for preprocessing
but still my c++ soln took time 3.7sec whereas java gave tle

You dont need to check logic. Jst see if am doing any stupidity which is increasing my program’s exec time
am using Fast IO from geeksforgeeks for taking inputs and StringBuilder for output
also tried BufferedWriter, PrintWriter

JAVA’s ArrayList and HashMap(to be specific the whole java.util package) are really inefficient, its not always amortized O(1) operation. I see that you are using extensively these classes in your code(e.g. using HashMap for child count which could have had been easily replaced with arrays).

Anyways you can have a look at my solution

1 Like

That is because even after using ios_base endl flushes the output everytime it’s encountered, that’s why it makes the total time slow for a solution with huge number of outputs.
So to make program use ios_base, it fasten the input process even better than scanf, and also use ‘\n’ instead of endl;

1 Like

can anyone please provide python solution .

Can someone please explain the 3, 4, 5 and 6 question in more detail ?

If anyone’s still stuck, look at my explanation

3 Likes

Thanks a lot, it’s a great explanation

1 Like

I did it using binary lifting for each query(besides lca), so it cost me logn per query.

1 Like

Why are we adding the number of paths passing through c1 and c2 and u ??? Can someone please explain with the help of an example ?

@teja349 If possible can you please add pictures for visualisation in editorial.

Only cin.tie(NULL) works the same way as both statements. cout.tie(NULL) is redundant if the former is used.

1 Like

@teja349 Waiting for pictures :frowning: editorial is still not clear without pictures

see his explanation

1 Like

You mean that using cin.tie(NULL) is same as using both the statements cin.tie(NULL) and cout.tie(NULL) ?
we just need to use cin.tie(NULL) because it will work for both whereas cout.tie(NULL) won’t work for both ?

I was writing the solution in JAVA. It was getting TLE. So, I commented all of my logic just reading the input and its still getting TLE issue. What is the wrong with JAVA goin on in CODECHEF.
https://www.codechef.com/viewsolution/25435529

For each query, you declare a boolean array of size N. Complexity = O(NQ).

I cannot see the tree image which explains 6 questions paths, i am unable to understand it like this, what should i do?

2 Likes