有大佬能帮忙吗，在线加急，在此膜拜 题目描述 你有一张 ? n 个结点， ? m 条边的有点权，无边权的无向图。对于每一个 1 ≤ ? ≤ ? 1≤x≤n，回答是否存在一条从 1 1 到 ? x 的路径，使得路径上的点权下凸。

称一个序列 ? 1 , … , ? ? a 1 ​ ,…,a k ​ 是下凸的，当且仅当对任意 2 ≤ ? < ? 2≤i<k， ? ? − 1 + ? ? + 1 ≥ 2 ? ? a i−1 ​ +a i+1 ​ ≥2a i ​ 。

输入格式 输入的第一行有两个正整数 ? , ? n,m，表示图的点数和边数。

第二行有 ? n 个自然数 ℎ 1 , ℎ 2 , … , ℎ ? h 1 ​ ,h 2 ​ ,…,h n ​ ，依次表示所有点的点权。

之后有 ? m 行，每行有两个正整数 ? , ? u,v，表示一条边。

输出格式 输出一行 ? n 个正整数，其中如果存在从 1 1 到 ? x 的下凸路径则第 ? x 个正整数为 1 1，否则为 0 0。

样例 #1 样例输入 #1 4 4 6 5 0 9 1 2 2 3 3 4 4 2 样例输出 #1 1 1 0 1 提示 【样例解释】

1 → 1 1→1 的路径点权序列为 6 6，下凸。

1 → 2 1→2 的路径点权序列为 6 , 5 6,5，下凸。

1 → 2 → 3 1→2→3 的点权序列为 6 , 5 , 0 6,5,0，其中 6 + 0 < 2 × 5 6+0<2×5，所以不下凸。

1 → 2 → 4 → 3 1→2→4→3 的点权序列为 6 , 5 , 9 , 0 6,5,9,0，其中 5 + 0 < 2 × 9 5+0<2×9，所以不下凸。

1 → 2 → 4 1→2→4 的点权序列为 6 , 5 , 9 6,5,9，其中 6 + 9 ≥ 2 × 5 6+9≥2×5，所以下凸。

【数据范围】

子任务编号 ? ≤ n≤ ? ≤ m≤ 特殊性质 分值 1 1 8 8 28 28 13 13 2 2 80 80 2000 2000 10 10 3 3 1000 1000 6 6 4 4 2 × 1 0 5 2×10 5

= ? − 1 =n−1 ? ?

? , ? ?

? + 1 u i ​ =i,v i ​ =i+1 3 3 5 5 图连通 6 6 6 6 5 × 1 0 5 5×10 5

ℎ 1 h 1 ​ 是 ℎ h 最小值 17 17 7 7 ℎ ? ≤ 1 0 5 h i ​ ≤10 5

18 18 8 8 27 27 对于全体数据，保证 1 ≤ ? ≤ 2 × 1 0 5 1≤n≤2×10 5 ， 1 ≤ ? ≤ 5 × 1 0 5 1≤m≤5×10 5 ， 0 ≤ ℎ ? ≤ 1 0 18 0≤h i ​ ≤10 18 。