No.3386 Up Down Hiking (Python)
タグ : / 解いたユーザー数 9
作問者 :
Rho
Problem Statement
naka9 is planning a trip to the TSG Kingdom, which is famous for its magnificent scenery.
The TSG Kingdom has points numbered from 1 to $N$ and $M$ roads connecting them. The $i$-th road bidirectionally connects distinct points $a_i$ and $b_i$. At most 1 road directly connects any pair of points.
Also, each point $i$ has the $H_i$-th lowest elevation among these $N$ points. Here, the $H_i$ are distinct.
naka9 is thinking of hiking from point 1 to point $N$, but does not want to go up and down many times.
So naka9 wants to find a route that goes uphill up to some point and goes downhill from that point on. That is, a route walking through points $v_1(=1),v_2,\dots,v_K(=N)$ in order such that, for some $1\leq j\leq K$, $H_{v_1},\dots,H_{v_j}$ is monotonically increasing and $H_{v_j},\dots,H_{v_K}$ is monotonically decreasing.
Output the length of the longest route among the routes satisfying this condition. 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$ exists if there exists an integer sequence $v_1,v_2,\ldots,v_K$ consisting of numbers between $1$ and $N$, inclusive, that satisfies the following conditions.- $v_1=1$
- $v_K=N$
- For $i=1,2,\ldots,K-1$, there exists a road directly connecting point $v_i$ and point $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 inputs are integers
Output
Output the length of the route satisfying the condition. If no such route exists, output -1. Print a newline at the end.
Score
Intended solution: $236$ 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
Sample
Sample 1
Input
3 2 1 3 2 1 2 2 3
Output
3
You can go uphill from point 1 to point 2, and then reach point 3 going only downhill from there.
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 point 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 point 1 and point $N$ multiple times.
Sample 5
Input
4 2 1 2 3 4 1 2 3 4
Output
-1
There may be no route from point $1$ to point $N$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。