AT_abc342_e [ABC342E] Last Train

题目描述

AtCoder 国有 $N$ 个车站，分别为车站 $1$、车站 $2$、……、车站 $N$。

AtCoder 国中存在 $M$ 条列车信息。第 $i$ 条信息（$1\leq i\leq M$）由六个正整数 $(l_i, d_i, k_i, c_i, A_i, B_i)$ 组成，表示如下内容：

• 对于 $t=l_i, l_i+d_i, l_i+2d_i, \ldots, l_i+(k_i-1)d_i$ 的每一个 $t$，都有如下列车：
  • 在时刻 $t$ 从车站 $A_i$ 出发，在时刻 $t+c_i$ 到达车站 $B_i$。

除此之外，不存在其他列车，也无法通过其他方式从一个车站移动到另一个不同的车站。 此外，换乘所需时间可以忽略不计。

定义从车站 $S$ 到达车站 $N$ 的最晚出发时刻为 $f(S)$。 更严格地说，$f(S)$ 是满足以下所有条件的整数四元组序列 $\big((t_i, c_i, A_i, B_i)\big)_{i=1,2,\ldots,k}$ 中 $t$ 的最大值：

• $t\leq t_1$
• $A_1=S, B_k=N$
• 对所有 $1\leq i<k$，有 $B_i=A_{i+1}$
• 对所有 $1\leq i\leq k$，存在在时刻 $t_i$ 从车站 $A_i$ 出发、在时刻 $t_i+c_i$ 到达车站 $B_i$ 的列车
• 对所有 $1\leq i<k$，有 $t_i+c_i\leq t_{i+1}$

若不存在这样的 $t$，则 $f(S)=-\infty$。

请计算 $f(1), f(2), \ldots, f(N-1)$。

输入格式

输入按以下格式从标准输入给出。

$N$ $M$
$l_1$ $d_1$ $k_1$ $c_1$ $A_1$ $B_1$
$l_2$ $d_2$ $k_2$ $c_2$ $A_2$ $B_2$
$\vdots$
$l_M$ $d_M$ $k_M$ $c_M$ $A_M$ $B_M$

输出格式

输出 $N-1$ 行。第 $k$ 行若 $f(k)\neq -\infty$，则输出 $f(k)$，否则输出 Unreachable。

输入输出样例 #1

输入 #1

6 7
10 5 10 3 1 3
13 5 10 2 3 4
15 5 10 7 4 6
3 10 2 4 2 5
7 10 2 3 5 6
5 3 18 2 2 3
6 3 20 4 2 1

输出 #1

55
56
58
60
17

输入输出样例 #2

输入 #2

5 5
1000000000 1000000000 1000000000 1000000000 1 5
5 9 2 6 2 3
10 4 1 6 2 3
1 1 1 1 3 5
3 1 4 1 5 1

输出 #2

1000000000000000000
Unreachable
1
Unreachable

输入输出样例 #3

输入 #3

16 20
4018 9698 2850 3026 8 11
2310 7571 7732 1862 13 14
2440 2121 20 1849 11 16
2560 5115 190 3655 5 16
1936 6664 39 8822 4 16
7597 8325 20 7576 12 5
5396 1088 540 7765 15 1
3226 88 6988 2504 13 5
1838 7490 63 4098 8 3
1456 5042 4 2815 14 7
3762 6803 5054 6994 10 9
9526 6001 61 8025 7 8
5176 6747 107 3403 1 5
2014 5533 2031 8127 8 11
8102 5878 58 9548 9 10
3788 174 3088 5950 3 13
7778 5389 100 9003 10 15
556 9425 9458 109 3 11
5725 7937 10 3282 2 9
6951 7211 8590 1994 15 12

输出 #3

720358
77158
540926
255168
969295
Unreachable
369586
466218
343148
541289
42739
165772
618082
16582
591828

说明/提示

限制条件

• $2\leq N\leq 2\times 10^5$
• $1\leq M\leq 2\times 10^5$
• $1\leq l_i, d_i, k_i, c_i\leq 10^9\ (1\leq i\leq M)$
• $1\leq A_i, B_i\leq N\ (1\leq i\leq M)$
• $A_i\neq B_i\ (1\leq i\leq M)$
• 输入均为整数

样例解释 1

AtCoder 国中运行的列车如下图所示（图中未包含发车和到达时间信息）。

以车站 $2$ 到车站 $6$ 的最晚到达时刻为例。如下图所示，可以在时刻 $56$ 从车站 $2$ 出发，依次经过车站 $2\rightarrow 3\rightarrow 4\rightarrow 6$ 到达车站 $6$。

无法在时刻 $56$ 之后从车站 $2$ 出发到达车站 $6$，因此 $f(2)=56$。

样例解释 2

存在一列在时刻 $10^{18}$ 从车站 $1$ 出发、在时刻 $10^{18}+10^9$ 到达车站 $5$ 的列车。此后没有更晚出发的列车，因此 $f(1)=10^{18}$。
另外，在时刻 $14$ 从车站 $2$ 出发、在时刻 $20$ 到达车站 $3$ 的列车，既由第 $2$ 条信息，也由第 $3$ 条信息保证存在。
如上所述，可能存在多条信息重复描述同一列车。

由 ChatGPT 4.1 翻译