Блог пользователя ssi7415

Автор ssi7415, 11 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +24
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится -31 Проголосовать: не нравится

lol, singaporeans know what computer is

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    As I know, in practice, Fibonacci heap is not much faster than binary heap, sometimes it's even slower.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
11 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Last test (4.2) in the 'sightseeing' problem is incorrect — it contains edge 1 2 200000, while quality of the road should be not greater than 10^5.