103354: [Atcoder]ABC335 E - Non-Decreasing Colorful Path

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $525$ points

Problem Statement

There is a connected undirected graph with $N$ vertices and $M$ edges, where the $i$-th edge connects vertex $U_i$ and vertex $V_i$ bidirectionally.
Each vertex has an integer written on it, with integer $A_v$ written on vertex $v$.

For a simple path from vertex $1$ to vertex $N$ (a path that does not pass through the same vertex multiple times), the score is determined as follows:

  • Let $S$ be the sequence of integers written on the vertices along the path, listed in the order they are visited.
  • If $S$ is not non-decreasing, the score of that path is $0$.
  • Otherwise, the score is the number of distinct integers in $S$.

Find the path from vertex $1$ to vertex $N$ with the highest score among all simple paths and print that score.

What does it mean for $S$ to be non-decreasing? A sequence $S=(S_1,S_2,\dots,S_l)$ of length $l$ is said to be non-decreasing if and only if $S_i \le S_{i+1}$ for all integers $1 \le i < l$.

Constraints

  • All input values are integers.
  • $2 \le N \le 2 \times 10^5$
  • $N-1 \le M \le 2 \times 10^5$
  • $1 \le A_i \le 2 \times 10^5$
  • The graph is connected.
  • $1 \le U_i < V_i \le N$
  • $(U_i,V_i) \neq (U_j,V_j)$ if $i \neq j$.

Input

The input is given from Standard Input in the following format:

$N$ $M$
$A_1$ $A_2$ $\dots$ $A_N$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_M$ $V_M$

Output

Print the answer as an integer.


Sample Input 1

5 6
10 20 30 40 50
1 2
1 3
2 5
3 4
3 5
4 5

Sample Output 1

4

The path $1 \rightarrow 3 \rightarrow 4 \rightarrow 5$ has $S=(10,30,40,50)$ for a score of $4$, which is the maximum.


Sample Input 2

4 5
1 10 11 4
1 2
1 3
2 3
2 4
3 4

Sample Output 2

0

There is no simple path from vertex $1$ to vertex $N$ such that $S$ is non-decreasing. In this case, the maximum score is $0$.


Sample Input 3

10 12
1 2 3 3 4 4 4 6 5 7
1 3
2 9
3 4
5 6
1 2
8 9
4 5
8 10
7 10
4 6
2 8
6 7

Sample Output 3

5

Input

Output

得分:$525$分 部分 问题描述 有一个包含$N$个顶点和$M$条边的连通无向图,其中第$i$条边双向连接顶点$U_i$和顶点$V_i$。 每个顶点上都写有一个整数,其中顶点$v$上写有整数$A_v$。 对于从顶点$1$到顶点$N$的简单路径(一条不通过同一个顶点多次的路径),其分数的确定方法如下: - 让$S$表示沿着路径上的顶点所写的整数序列,按访问顺序列出。 - 如果$S$不是非递减的,那么该路径的分数为$0$。 - 否则,分数为$S$中不同整数的数量。 在所有简单路径中,找到从顶点$1$到顶点$N$的分数最高的路径,并打印该分数。
什么是$S$的非递减性? 长度为$l$的序列$S=(S_1,S_2,\dots,S_l)$被认为是递减的,当且仅当对于所有整数$1 \le i < l$,都有$S_i \le S_{i+1}$。
部分 约束 - 所有输入值都是整数。 - $2 \le N \le 2 \times 10^5$ - $N-1 \le M \le 2 \times 10^5$ - $1 \le A_i \le 2 \times 10^5$ - 图是连通的。 - $1 \le U_i < V_i \le N$ - 如果$i \neq j$,则$(U_i,V_i) \neq (U_j,V_j)$。 部分 输入 输入以标准输入的以下格式给出: $N$ $M$ $A_1$ $A_2$ $\dots$ $A_N$ $U_1$ $V_1$ $U_2$ $V_2$ $\vdots$ $U_M$ $V_M$ 部分 输出 打印答案作为整数。 部分 样例输入1 5 6 10 20 30 40 50 1 2 1 3 2 5 3 4 3 5 4 5 部分 样例输出1 4 路径$1 \rightarrow 3 \rightarrow 4 \rightarrow 5$有$S=(10,30,40,50)$,得分为$4$,这是最大的。 部分 样例输入2 4 5 1 10 11 4 1 2 1 3 2 3 2 4 3 4 部分 样例输出2 0 没有从顶点$1$到顶点$N$的简单路径,使得$S$是非递减的。在这种情况下,最大分数为$0$。 部分 样例输入3 10 12 1 2 3 3 4 4 4 6 5 7 1 3 2 9 3 4 5 6 1 2 8 9 4 5 8 10 7 10 4 6 2 8 6 7 部分 样例输出3 5

加入题单

上一题 下一题 算法标签: