問題一覧 > ショートコード

No.3385 Up Down Hiking (C++)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 6
作問者 : tRue / テスター : alcea naka9 Rho 259-Momone
お気に入りにしたユーザー ProblemId : 12860 / 自分の提出
問題文最終更新日: 2025-11-22 12:42:40
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest TSG LIVE! 15 コードゴルフコンテスト (順位表) の他の問題:

Problem Statement

naka9 is planning a trip to the Kingdom of TSG, which is famous for its magnificent scenery.

The Kingdom of TSG has locations numbered from 1 to $N$ and $M$ roads connecting them, where the $i$-th road bidirectionally connects distinct locations $a_i$ and $b_i$. There is at most 1 road directly connecting any pair of locations.

Also, each location $i$ has the $H_i$-th lowest elevation among these $N$ locations. Here, the $H_i$ are pairwise distinct.

naka9 is thinking of hiking from location 1 to location $N$, but does not want to go up and down many times.

Therefore, naka9 wants to find a route that goes up to some location and goes down from that location onward. That is, when walking through locations $v_1(=1),v_2,\dots,v_K(=N)$ in order, there must exist some $1\leq j\leq K$ such that $H_{v_1},\dots,H_{v_j}$ is monotonically increasing and $H_{v_j},\dots,H_{v_K}$ is monotonically decreasing.

Among the routes satisfying this condition, output the length of the longest route. If no route satisfies the condition, output that fact.

Definition of a route and its length A route of length $K$ from vertex $1$ to $N$ is said to exist if there exists an integer sequence $v_1,v_2,\ldots,v_K$ consisting of numbers between $1$ and $N$, inclusive, satisfying the following conditions.
  • $v_1=1$
  • $v_K=N$
  • For $i=1,2,\ldots,K-1$, there exists a road directly connecting location $v_i$ and location $v_{i+1}$

Input

$N\ M$
$H_1\ H_2\ \cdots\ H_N$
$a_1\ b_1$
$\vdots$
$a_M\ b_M$
  • $2\leq N\leq 10^5$
  • $1\leq M\leq \min(10^5,\frac{N(N-1)}{2})$
  • $1\leq H_i\leq N \quad (1\leq i\leq N)$
  • $H_i\neq H_j$ if $i\neq j$
  • $1\leq a_i<b_i\leq N\quad(1\leq i\leq M)$
  • $(a_i,b_i)\neq(a_j,b_j)$ if $i\neq j$
  • All input values are integers.

Output

Output the length of the route satisfying the condition. If no such route exists, output -1. Also, print a newline at the end.

Score

Intended solution: $297$ bytes

Score formula When the code length of a submitted source code is $x$ and the code length of the intended solution of this problem is $y$, the score of that source code is calculated as follows.
  • If $y\leq x$: $\lfloor100\exp(-0.012(x-y))\rfloor$ points
  • If $x<y$: $101$ points
The score of this problem is the maximum of the scores of the source codes submitted to this problem.

Sample

Sample 1
Input
3 2
1 3 2
1 2
2 3
Output
3

You can go up from location 1 to location 2, and from there reach location 3 by only going down.

Sample 2
Input
3 2
2 1 3
1 2
2 3
Output
-1

No route satisfies the condition, so output -1.

Sample 3
Input
10 20
1 9 5 4 7 3 8 6 10 2
7 9
1 2
3 10
1 10
6 8
7 8
1 3
4 6
4 8
1 6
3 6
7 10
5 10
2 6
1 9
9 10
2 4
8 10
3 5
5 7
Output
10

You may pass through the same location multiple times.

Sample 4
Input
4 4
2 3 4 1
1 2
2 3
3 4
1 4
Output
6

You may pass through location $1$ and location $N$ multiple times.

Sample 5
Input
4 2
1 2 3 4
1 2
3 4
Output
-1

There may be no route from location $1$ to location $N$.

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