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.

or at least your solution complexity..

Edited by author 20.04.2007 02:42

hm.. I think your solution correct
can you explain how to use bs
I can send to you c++ prog wich read 10Mb ~ 0.6-0.7 sec

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.

Thank you
but why it works, is it standart method?

Problem called Minimal Ratio Spanning Tree, and brute binary search got TLE. But i think, using Mediggo method it's possible to solve it in time.

http://theory.stanford.edu/~megiddo/pdf/rational.html

I think only optimisation is needed
You will call SpanTree O(n^2) not more then 50 times
It takes less then 2 sec

You can speed up input several times
If write like this
scanf("%d%d%d%d\n",&a,&b,&c,&d);
on 10Mb it will work ~3 sec

TLE 34 :(
I used mix of binary search and Mediggo's approach.

>>You will call SpanTree O(n^2) not more then 50 times
And how to solve MST in O(n^2)?

Edited by author 28.04.2007 16:05

I used just plain binary search and computed the MST with Prim's algorithm. No complicated data structures or Megiddo's aproach are needed here. Just some small optimizations on the code.

Thanks a lot! I finally solved it in 0.375. But can't optimize to your 0.359 :)

Edited by author 04.09.2008 20:32

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 :)

Binary search works VERY fast if you combine it with disjoint sets

It does not matter here because edge-sorting step consumes O(N^2*log(N)) time.