[arc038_d]有向グラフと数

ID: 2254

传统题

2000ms

256MiB

难度: 9

上传者:

标签>

3000+

$N$ 頂点 $M$ 辺の有向グラフがあります。このグラフの頂点 $i$ には、整数 $X_i$ が書かれています。ゲーム好きな兄妹がこのグラフと $1$ つのチェスの駒を使ってゲームをしようとしています。

最初、駒を頂点 $1$ に置く。
プレイヤーは自分のターンに、以下のいずれかちょうど $1$ $1$ つの操作をしなければならない。
- 移動 : 駒を別の頂点にちょうど $1$ 回移動させる。駒が頂点 $i$ にある場合は、頂点 $i$ から頂点 $j$ に向かう辺があるような頂点 $j$ にのみ移動させることができる。
- 終了宣言 : ゲームを終了させる。
交互にターンを繰り返し、どちらかのプレイヤーが終了宣言をするか、後手が $10^9$ 回移動をさせた直後の時点でゲームは終了となり、その時点で駒がある頂点に書かれた整数がこのゲームの スコア となる。

先手のプレイヤーがスコアを出来るだけ大きくするような行動を取り、後手のプレイヤーがスコアを出来るだけ小さくするような行動を取るとき、ゲームのスコアはいくつになるでしょうか？

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $X_1$ $X_2$ ... $X_N$ $A_1$ $B_1$ $A_2$ $B_2$ : $A_M$ $B_M$

$1$ 行目には、グラフの頂点の個数を表す整数 $N (1 ≦ N ≦ 100,000)$ と辺の個数を表す $M (1 ≦ M ≦ 200,000)$ が空白区切りで与えられる。
$2$ 行目には、各頂点に書かれた整数を表す $N$ 個の整数が空白区切りで与えられる。このうち $i (1 ≦ i ≦ N)$ 番目の整数 $X_i (0 ≦ X_i ≦ 10^9)$ は、頂点 $i$ に書かれた整数を表す。
$3$ 行目からの $M$ 行には、辺の情報が与えられる。このうち $i (1 ≦ i ≦ M)$ 行目には、 $2$ つの整数 $A_i,B_i (1 ≦ A_i ≦ N, 1 ≦ B_i ≦ N, A_i \\neq B_i)$ が空白区切りで与えられる。これは、グラフに頂点 $A_i$ から頂点 $B_i$ に向かう有向辺があることを表す。ただし、同じ辺が $2$ 回与えられることはないこと、すなわち $p \\neq q$ のとき $A_p \\neq A_q$ または $B_p \\neq B_q$ が成り立つことが保証される。

この問題には部分点が設定されている。

ゲームのスコアを $1$ 行に出力せよ。出力の末尾に改行を入れること。

この例では、ゲームは以下のように進行します。

先手がどのような行動を取っても、後手が適切な行動を取ることによってスコアを $2$ より大きくすることは出来ません。

また、後手がどのような行動を取っても、先手が適切な行動を取ることによってスコアを $2$ より小さくすることは出来ません。

この例では、ゲームは以下のように進行します。

先手がどのような行動を取っても、後手が適切な行動を取ることによってスコアを $1$ より大きくすることは出来ません。

また、後手がどのような行動を取っても、先手が適切な行動を取ることによってスコアを $1$ より小さくすることは出来ません。

#arc038d. [arc038_d]有向グラフと数