I have solved this problem is Java, by now it is the only solution in this not fast language. :-) My solution was rather advanced, real arithmetics only on output, but it used almost all given time 4.75 / 5.00 s.

Then I saw statistics of this problem. There are solutions that work much less than 1s. Is it advantage of fast C++ compiler, is it advantage of hand-written data structures (I used standard PriorityQueue) or is algorithm used much more advanced than mine?

Could anyone explain optimizations of really (<1s) fast solution?