Hi all,
Singapore has recently concluded its 2014 National Olympiad in Informatics (on 8 March 2014), which is used to select the team to represent Singapore at 2014 IOI.
All tasks (4 of them) can be found here and all test data can be found here.
Edit: Just a note here, the time limits and memory limit of the problems can be found on the first page of the document (notes, point 5).
Enjoy the tasks!
lol, singaporeans know what computer is
Is Fibonacci heap expected for problem 2.4? Input seems to be extremely large. And it is not like IOI or topcoder, which are io-free, so your program must read more than 1M integers. (Maybe pascal code TLE only for reading, that's not fair!)
As I know, in practice, Fibonacci heap is not much faster than binary heap, sometimes it's even slower.
I think sorting the edges by the decreasing(non-increasing) order of the weight and using disjont-set data structure is enough to solve this. Iterate the edges in the sorted order, connect the edge, ans find if the vertex is in the same component with vertex 1. Then we will be able to answer all the queries
Last test (
4.2) in the 'sightseeing' problem is incorrect — it contains edge1 2 200000, while quality of the road should be not greater than10^5.