No.2100 [Cherry Alpha C] Two-way Steps
タグ : / 解いたユーザー数 96
作問者 : 👑
Kazun
/ テスター :
butsurizuki
sapphire__15
Problem Statement
There are $N$ platforms. They are named platform $1$, platform $2$, $\cdots$, platform $N$, in this order. The height of platform $i~(1 \leq i \leq N)$ is $H_i$.
There are also $M$ staircases, and the $j~(1 \leq j \leq M)$-th staircase bidirectionally connects platform $X_j$ and platform $Y_j$ with a staircase of $\left|H_{X_j}-H_{Y_j} \right|$ steps. Note that the $2$ platforms connected by a staircase never have equal heights.
Using these staircases, one can move from one platform to another. Strictly speaking, a move from platform $a$ to platform $b$ using a staircase is as follows:
- If $H_a < H_b$, move from platform $a$ to platform $b$ by going up $(H_b-H_a)$ steps.
- If $H_a > H_b$, move from platform $a$ to platform $b$ by going down $(H_a-H_b)$ steps.
Now, there are Cherry-chan and Zelkova-kun. The situations, goals, and conditions of these 2 people are as follows.
- Cherry-chan: She is initially on platform $1$. She wants to get to platform $N$ by moving through $0$ or more staircases. However, when moving from platform $a$ to platform $b$ using a staircase, $a \lt b$ must hold. That is, each move must increase the platform number.
- Zelkova-kun: He is initially on platform $N$. He wants to get to platform $1$ by moving through $0$ or more staircases. However, when moving from platform $a$ to platform $b$ using a staircase, $a \gt b$ must hold. That is, each move must decrease the platform number.
- Common to the 2 people: When moving between platforms using staircases, they cannot go up staircases 2 times in a row.
Answer the following question for each of Cherry-chan and Zelkova-kun.
- Is it possible to achieve the goal by moving between platforms while satisfying the conditions? Also, since the $2$ people both love going up stairs, if the goal can be achieved, find the maximum total number of steps gone up during the movement (steps gone down are not counted).
Constraints
- $2 \leq N \leq 10^5$
- $1 \leq M \leq 1.5 \times 10^5$
- $0 \leq H_i \leq 10^9 \quad (1 \leq i \leq N)$
- $1 \leq X_j \lt Y_j \leq N \quad (1 \leq j \leq M)$
- $H_{X_j} \neq H_{Y_j} \quad (1 \leq j \leq M)$
- $j \neq k \Rightarrow (X_j, Y_j) \neq (X_k, Y_k) \quad (1 \leq j \leq M, 1 \leq k \leq M)$
- All inputs are integers.
Input
$N$ $M$ $H_1$ $\cdots$ $H_N$ $X_1$ $Y_1$ $\vdots$ $X_M$ $Y_M$
Output
The output consists of $2$ lines.
- On line $1$, for Cherry-chan, print
-1if it is impossible to move between platforms while satisfying the conditions; otherwise, print the maximum total number of steps gone up. - On line $2$, for Zelkova-kun, print
-1if it is impossible to move between platforms while satisfying the conditions; otherwise, print the maximum total number of steps gone up.
Do not forget the newline at the end.
Sample
Sample 1
Input
5 5 0 10 15 5 20 1 5 1 2 2 3 3 4 4 5
Output
20 10
Cherry-chan and Zelkova-kun can achieve their goals by moving as follows, and these moves maximize the total number of steps gone up.
- Cherry-chan: platform $1$ $\to$ platform $5$ (going up $20$ steps)
- Zelkova-kun: platform $5$ $\to$ platform $4$ $\to$ platform $3$ $\to$ platform $2$ $\to$ platform $1$ (going up $10$ steps)
Note that Cherry-chan cannot move as follows.
- Cherry-chan ($\times$): platform $1$ $\to$ platform $2$ $\to$ platform $3$ $\to$ platform $4$ $\to$ platform $5$
Sample 2
Input
3 2 4 6 46 1 2 2 3
Output
-1 0
- Cherry-chan: She cannot get to platform $N$ while satisfying the conditions. Thus,
-1must be printed. - Zelkova-kun: Note that steps gone down are not counted.
Sample 3
Input
8 10 31 41 59 26 53 58 97 93 1 8 2 7 3 5 1 4 5 8 4 5 2 5 6 7 4 7 3 7
Output
62 5
Sample 4
Input
4 1 1 2 3 4 2 3
Output
-1 -1
In the first place, platform $1$ and platform $N$ are not necessarily connected by staircases, even indirectly.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。