Binary search over A such that Z(A) = 0 gives TL 30. Is it necessary to use sparsification or other sophisticated methods? When m = 500000, n = 1000 reading of input data (~10mb) takes about 2.5 sec. I'm wonder how could people to solve it in 0.6 sec..
Just ideas or links what should i read to solve it.
Assign with each edge weight function w(x) = a - bx, where a = numerator, b - denominator. Let z(x) weight of minimal spanning tree at point x. If we find such x, that z(x) = 0 (such value always exists), x will be answer.
I constantly got with binary search TL6. Then I replaced binary search with iterative approach. I.e. build MST tree for x=1e+6, then build MST with whatever ratio previous tree had. Proceed until improvement is >1e-8. Now AC :)