問題一覧 > 通常問題

No.1382 Travel in Mitaru city

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 61
作問者 : 蜜蜂蜜蜂 / テスター : cardano1016cardano1016 MitarushiMitarushi
1 ProblemId : 5869 / 出題時の順位表
問題文最終更新日: 2021-02-08 08:52:20

問題文

ミタル市には、$\ N\ $個の街と$\ M\ $本の道路があります。
$i\ $番目$\ (1\leq i\leq N)\ $の街には$\ p_i\ $人の人が住んでいます。
また、$\ i\ $番目$\ (1\leq i\leq M)\ $の道路は$\ a_i\ $番目の街と$\ b_i\ $番目の街を双方向に結んでいます。
任意の$\ 2\ $つの街の組について、それらを直接結んでいる道路が高々$\ 1\ $本であることが保証されます。

あなたは変数$\ X,Y\ $を持っていて、最初は街$\ S\ $にいます。また初期状態では$\ X=p_S,Y=0\ $が成立しています。

これからあなたは以下の行動を続けます。

    現在いる街と道路で直接結ばれている街を$\ 1\ $つ選び、その街へ行く。その街が$\ i\ $番目の街として、$\ X>p_i\ $ならば$\ X=p_i\ $とし、$\ Y\ $に$\ 1\ $を足す。
あなたが$\ T\ $番目の街にいる場合、この行動を終了できます。(終了しないこともできます)

操作を終了した時点での$\ Y\ $が最大になるよう適当に行動をして操作を終了したとき、操作を終了した時点での$\ Y\ $はいくつになるかを求めてください。

入力

$N\ \ M\ \ S\ \ T$
$p_1\ \ p_2\ \ \cdots p_N$
$a_1\ \ b_1$
$a_2\ \ b_2$
$\vdots$
$a_M\ \ b_M$

  • $2 \leq N \leq 10^5$
  • $1 \leq M \leq 10^5$
  • $1 \leq S,T \leq N$
  • $S \neq T$
  • $1 \leq p_i \leq 10^9(1 \leq i \leq N)$
  • $1 \leq a_i < b_i \leq N(1 \leq i \leq M)$
  • $(a_i,b_i) \neq (a_j,b_j) (i \neq j)$
  • 入力は全て整数
  • $S\ $からいくつかの道を通って$\ T\ $に行けることは保証される

出力

操作を終了した時点での$\ Y\ $が最大になるよう適当に行動をして操作を終了したとき、操作を終了した時点での$\ Y\ $を出力し、最後に改行してください。

サンプル

サンプル1
入力
4 4 3 4
8 3 5 2
1 4
2 3
1 2
3 4
出力
2

街$\ 3,2,1,4\ $の順に移動すると$\ X\ $は$\ 5,3,3,2\ $と変化するので、$\ Y=2\ $となります。
$\ Y\ $が$\ 3\ $以上となるような移動の方法は存在しないので、答えは$2$となります。

サンプル2
入力
2 1 1 2
1 2021
1 2
出力
0

常に$\ X=1\ $となるため、常に$\ Y=0\ $となります。

サンプル3
入力
7 8 3 7
12 23 34 45 56 67 78
1 4
2 3
4 7
5 6
2 7
6 7
1 5
2 5
出力
2

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。