Singularity Cup P3 - Interplanetary Travel

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 3.0s
Memory limit: 512M

Problem types

Michael has discovered a strange planetary system consisting of N planets numbered from 1 to 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 kilometers away from the central star. The distance between any two planets i and j is equal to |D_i - D_j|. Michael starts on planet P and wants to visit all 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 such force fields, the ith of which is present on planet A_i and can be disabled on planet 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 can travel C kilometers when full. What is the smallest capacity C that will allow Michael to complete his journey?


1 \le N \le 10^6

0 \le M \le 10^6

1 \le A, B, P \le N

1 \le D_i \le 10^{18}

All 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

D_i \le 10^9

Subtask 2 [30%]

N, M \le 10^5

D_i \le 10^9

Subtask 3 [30%]

No additional constraints.

Input Specification

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

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

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

Output Specification

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

Sample Input

4 4 1
5 2 7 9
2 1
3 2
4 3
4 2

Sample Output



There are no comments at the moment.