JOI 2012/2013 Contest — Spaceships

Правка en1, от zscoder, 2016-07-27 17:49:30

Problem statement :

There are N planets in the galaxy. For each planet i, it has two possible states : empty, or it is connected to some other planet j ≠ i with a one-way path. Initially, each planet is in the empty state (i.e. there are no paths between any pair of planets)

There are three types of operations :

  1. If planet i is in empty state, connect it with planet j with a one-way path (i and j are distinct)

  2. If planet i is currently connected to planet j with a one-way path, remove that path. Consequently, planet i is now in empty state again

  3. For a pair of planets u, v, find a planet x such that one can travel from u to x and v to x. If there are multiple such planets, find the one where the total distance travelled by u and v is minimized (distance is the number of paths it passes through). If there are no solutions, output  - 1.

Q, N ≤ 106. Time limit is 10 seconds.

One of the official solutions uses splay tree to solve this problem, but I have no idea how it works (I haven't use splay trees before). Can anyone tell me how to use splay tree on this problem? Thanks.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский zscoder 2016-07-27 17:49:30 1194 Initial revision (published)