Singularity Cup P3 - Interplanetary Travel - Olympiads Online Judge

Singularity Cup P3 - Interplanetary Travel

View as PDF

Submit solution

All submissions

Best submissions

Points: 15 (partial)

Time limit: 3.0s

Memory limit: 512M

Author:

Mystical

Problem types

Michael has discovered a strange planetary system consisting of $N$ $N$ planets numbered from $1$ $1$ to $N$ $N$ .

The planets happen to orbit in such a way that they align in a straight line in front of the central star at all times. Each planet is located $D_i$ $D_{i}$ kilometers away from the central star. The distance between any two planets $i$ $i$ and $j$ $j$ is equal to $|D_i - D_j|$ $| D_{i} - D_{j} |$ . Michael starts on planet $P$ $P$ and wants to visit all $N$ $N$ planets, but his spaceship has a limited number of kilometers it can travel before needing to be refueled. His spaceship can be refueled back to full capacity after landing on any planet.

Additionally, some planets are locked behind force fields that prevent any visitors. These force fields can be deactivated remotely on designated planets. A planet may have multiple force fields, in which case all of them need to be deactivated before visiting it. There are $M$ $M$ such force fields, the $i$ $i$ th of which is present on planet $A_i$ $A_{i}$ and can be disabled on planet $B_i$ $B_{i}$ .

Michael needs to buy a fuel tank for his spaceship, but wants to minimize the size of the fuel tank in order to cut costs. A fuel tank of capacity $C$ $C$ can travel $C$ $C$ kilometers when full. What is the smallest capacity $C$ $C$ that will allow Michael to complete his journey?

Constraints

$1 \le N \le 10^6$ $1 \leq N \leq 10^{6}$

$0 \le M \le 10^6$ $0 \leq M \leq 10^{6}$

$1 \le A, B, P \le N$ $1 \leq A, B, P \leq N$

$1 \le D_i \le 10^{18}$ $1 \leq D_{i} \leq 10^{18}$

All $D_i$ $D_{i}$ are distinct.

All force fields are pairwise distinct.

Michael starts on a planet without any force fields and it is possible to disable all the force fields.

Subtask 1 [40%]

$N, M \le 5000$ $N, M \leq 5000$

$D_i \le 10^9$ $D_{i} \leq 10^{9}$

Subtask 2 [30%]

$N, M \le 10^5$ $N, M \leq 10^{5}$

$D_i \le 10^9$ $D_{i} \leq 10^{9}$

Subtask 3 [30%]

No additional constraints.

Input Specification

The first line of input contains integers $N$ $N$ , $M$ $M$ , and $P$ $P$ .

The next line of input contains $N$ $N$ space-separated integers representing $D$ $D$ . Planet $i$ $i$ is located at distance $D_i$ $D_{i}$ .

The next $M$ $M$ lines of input each contain integers $A$ $A$ and $B$ $B$ , representing a force field present on planet $A$ $A$ that can only be disabled from planet $B$ $B$ .

Output Specification

Output the smallest capacity $C$ $C$ that will allow Michael to travel to all the planets starting from planet $P$ $P$ .

Sample Input

Copy

Sample Output

Copy

Comments

There are no comments at the moment.