No.2242 Cities and Teleporters
タグ : / 解いたユーザー数 74
作問者 :
![shobonvip](https://pbs.twimg.com/profile_images/1630260134055383047/dOe_ZdIC.jpg)
![noya2](https://pbs.twimg.com/profile_images/1598325312500146176/4p3ZVMv9.jpg)
![Nachia](https://pbs.twimg.com/profile_images/1774764955763654656/4aQlUed4.jpg)
注意
入出力が多くなる場合があるので、高速な方法で入出力を行うことをおすすめします。
問題文
しょぼん国には 個の町があり、町は町 、町 、、町 と番号付けられています。 について、町 の標高は です。
しょぼん国は山地が多く不便なので、国王であるしょぼん君は全ての街に、それぞれの街から別の街に行けるテレポーターを設置しました。各 について、町 のテレポーターを使うと、町 から標高が 以下の別の任意の町に行くことができます。
個のクエリが与えられます。 番目のクエリでは、整数 が与えられるので、町 から町 にテレポーターを経由して行くときのテレポーターの使用回数の最小値を出力してください。ただし、町 から町 にテレポーターを経由して行くことができない場合は、-1
を出力してください。
制約
- 入力はすべて整数
-
入力
出力
行出力してください。 行目には、 番目のクエリの答えを出力してください。
サンプル
サンプル1
入力
4 1 7 2 9 6 1 7 3 4 1 3 1 2 2 3 2 4
出力
1 2 2 -1
番目のクエリにおいて、町 から町 にテレポーターで行くとき、テレポーターの使用回数の最小値は なので、 を出力します。
町 からは 標高が 以下の町に行くことが出来ますが、町 の標高は であるので、 回の移動で町 から町 に行くことは出来ません。よって、町 から町 に到達できるなら、 回以上移動することが必要です。実際、町 町 町 と移動できるため、最小の移動回数は になります。
番目のクエリにおいては、町 から町 にテレポーターで到達することができないため、-1
を出力します。
サンプル2
入力
2 100000000 1 1 1 2 1 2 2 1
出力
1 -1
テレポーターは双方向的ではないことに注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。