Try using vectors instead of map.
but in vector how would i got my previous calculated node ansers faster ??
Consider we just have k nodes in one level (where we do precomputation for each pair…)
Before doing that , store the indices of each node in a new vector … idx[node1] = 1… and so on
Then for each pair (node1 , node2) in that level precompute and store it in this index->idx[node1]*level_size + idx[node2] of the main vector at each level. (G[100005][index]).
So , when ever you get two ancestors that have been precalculated then use this index of vector G[level] , idx[ancestor1]*level_size + idx[ancestor2] from here you can get the value …
This is my code for reference
Hope this helps…
in this code you didnt used mod with 2^32?? why its so?? or i am missing something??
https://www.codechef.com/viewsolution/39720499
i have done with vector as well its still tle can you check it where its wrong??
I found one mistake that you are doing a[v].push_back(v). But I don’t know it will be useful or not.
its still showing tle done exactly like your code but why its showing tle for more cases now?
hey i got ac thanks for your guidence now by changing mod to unsigned int now may be that may be reason for them to give modulo from power of 2^32 because modulo is somewhat expensive …
link → CodeChef: Practical coding for everyone
Ok nice…
Can anyone please explain that where does my reasoning go wrong? Naive approach will perform O(NQ) operations which is approx. 10^11 operations which can be done in 2 sec.
So, naive approach should give AC
Online judge can perform only 10^8 operations in 1 second. So for 2 seconds it can only perform 2 * 10^8 operations. 10^11 operations would take 1000 seconds which is more than 15 minutes. Hope you got your doubts cleared.
1 Like
what is the difference between 2 and 3 subtasks?
Read this comment.!
1 Like
How unsigned int helps in 2^32 modulo?
Thanks in advance.
Any number data type such as int, uint, long long or u long long, rolls over to other side when an overlow occurs.
For example:
- The range of int is -{2^{31}} to {2^{31}-1}. But if you initialize an integer to be {2^{31}}, it’ll roll over to the -ve side, and the value stored would be -{2^{31}} .
- The same way, the range of uint is {0} to {2^{32}-1}. So instead of using % (modulo), as it is a costly operation, we simply use uint so the compiler automatically performs the modulo {2^{32}} by simply rolling over the range.
2 Likes
Why don’t you try removing modulo as discussed in this thread? After that if it doesn’t work then also try changing the block size a bit as sqrt(n) is not always optimal
Also try using unordered map and try optimizing it as discussed in this thread.
At least read the thread or google search before asking.
I don’t wanna spoon feed you.
Thanks a lot for the clarification
Which is better c++or java