i have used vector of pairs, and applied normal (inorder) approach,my ans for only last cases show TLE event though my approach is O(n). dont know where its getting stuck.please find out.
Link to my code:
https://www.codechef.com/viewsolution/19049541
I think the main time of your code is wasted on the function passing parameters, you should use the reference.
1 Like
why did it happen that when i changed my vector of pairs to vector of array,as we do in standard graph,it passed the TLE cases,(maybe something about indexing vs structure element),but is it wise to note it for future.Are there any other points to keep in mind,or it comes through experience? Or is it wise to globally declare elements as such
Passing vector as parameter takes O(N) time, where $N = $length of vector. This is “pass by value” which internally creates a new memory location and copies the contents of the variable there. Vector copying will take O(N) time. With arrays this is not a problem as we only pass the initial pointer (4 bytes) and this is a O(1) operation. Vectors should be passed by reference only in case of recursive functions. Otherwise it should be passed by reference or value depending on use-case. The complexity of your code is therefore O(N^2), explaining the TLE.
1 Like
thanks a lot!!. Nice explanation, I never considered the O(N) copying part on call by value.