Timeline

题目描述

贝茜在过去的 $M$ 天内参加了 $N$ 次挤奶活动（$1\le N\le 10^5$，$2 \le M \le 10^9$）。然而，她记不清每次活动分别发生在哪一天。 对于每次活动 $i = 1 \ldots N$，她只知道该活动不早于第 $S_i$ 天发生（$1\le S_i\le M$）。此外，贝茜还有 $C$ 条记忆（$1\le C\le 10^5$），每条用三元组 $(a,b,x)$ 描述，表示她记得活动 $b$ 至少在活动 $a$ 之后的 $x$ 天发生。 请你计算每次挤奶活动可能发生的最早日期。保证贝茜的记忆没有出错；换句话说，存在一种将活动安排到 $1\ldots M$ 天中的方案，使得她所有记忆对应的约束都能被满足。 计分： 测试点 2-4 满足 $N,C \le 10^3$。 测试点 5-10 没有额外限制。

输入格式

第一行输入包含 $N$、$M$ 和 $C$。 第二行包含 $N$ 个用空格分隔的整数 $S_1,S_2,\ldots, S_N$，每个都在范围 $1 \ldots M$ 内。 接下来 $C$ 行每行包含三个整数 $a$、$b$ 和 $x$，表示活动 $b$ 至少在活动 $a$ 之后的 $x$ 天发生。对于每一行，$a \neq b$，$a$ 和 $b$ 都在范围 $1 \ldots N$ 内，且 $x$ 在范围 $1 \ldots M$ 内。

输出格式

输出 $N$ 行，每行给出对应活动可能发生的最早日期。

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

1
6
3
8

提示

活动 2 至少在活动 1 之后五天发生，因此它不可能早于第 $1+5=6$ 天发生。活动 4 至少在活动 2 之后两天发生，因此它不可能早于第 $6+2=8$ 天发生。 题目作者：Mark Gordon

标签: USACO|2020|Gold

来源

USACO|2020|Gold