well, I guess this problem has a strict time limit for python (but then again, I’m no expert in python). this is the optimized code that is equivalent to what I’ve done in C++: http://www.codechef.com/viewsolution/4362878
alphaparticle: No, your solution is O(N^3 log(N)) - for each disconnected pair, you can end up checking all edges from one of them before breaking, and there can be a lot of them. It just has a really good constant and it’s hard to make testcases where it runs worst-case.
No, your solution is O(N^3 log(N)) - for each disconnected pair, you can end up checking all edges from one of them (you’re not doing one binseatch, you’re doing up to degree(u) binsearches) before breaking, and there can be a lot of them. It just has a really good constant and it’s hard to make testcases where it runs worst-case.
It seems my optimisations were correct!! Cuts the runtime by HALF
Here is my submission. I’ll leave it to you to understand why this works :). Common sense actually