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 :
If planet i is in empty state, connect it with planet j with a one-way path (i and j are distinct)
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
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.
The problem seems interesting. My only idea of splay tree usage would be Link-Cut Trees, though a solution with them is not obvious. The structure of the resulting graph can be represented as a forest but the trees' roots can be cycles which makes stuff complicated.
Can you provide a link with the author solution (code) ?
Sure, here is the Splay Tree solution.
After some google translates and browsing the editorial of the problem (277 slides in Japanese) I finally found what I wanted to. There's an additional constraint that you did not mention — cycles can't be formed. It's an extremely important constraint since now the whole structure of the graph indeed becomes a forest and Link-Cut Trees start making a lot more sense.
Actually this is said in first paragraph:
I believe empty state refers to not having an outgoing edge? A single vertex can have arbitrarily many ingoing edges and still be in an empty state. This constraint does not imply the lack of cycles.
I don't understand how the author's Splay Tree solution work. Can you enlighten me? (I don't get why there is splay() and splaySolid())
I'm not sure how it works either. I believe it is a toned-down version of Link-Cut Tree (if you're not familiar with those, you'll have to read some).
Once we know that cycles can't form we're basically given the problem of keeping a dynamic forest and answering LCA questions. Link-Cut Trees are a great specifically for such problems, though I'm not too good with them and hence I don't understand author's solution.
The Japanese editorial however mentions two methods — one is Link-Cut and the other is Euler Path Trees which I find much easier to understand in this problem, even if it is harder to implement.
Looks like splaySolid() is usually called "splay" and splay() is usually called "expose".
UPD: I've missed that the graph should be directed.