Last Train

题目描述

在 AtCoder 的国家中，有 $N$ 个车站：车站 $1$、车站 $2$、$\ldots$、车站 $N$。 给出关于该国火车的 $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$ 从车站 $A _ i$ 出发，并在时间 $t+c _ i$ 到达车站 $B _ i$。

除此之外不存在其他火车，并且除乘坐火车外无法从一个车站移动到另一个车站。
另外，假设换乘所需时间可以忽略不计。 令 $f(S)$ 为能够从车站 $S$ 到达车站 $N$ 的最晚到达时间。
更精确地，$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$ $B _ i=A _ {i+1}$ 对所有 $1\leq i\lt k$ 成立， 对所有 $1\leq i\leq k$，存在一列在时间 $t _ i$ 从车站 $A _ i$ 出发并在时间 $t _ i+c _ i$ 到达车站 $B _ i$ 的火车。 $t _ i+c _ i\leq t _ {i+1}$ 对所有 $1\leq i\lt k$ 成立。

如果不存在这样的 $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)$（若 $f(k)\neq-\infty$），若 $f(k)=-\infty$ 则输出 $Unreachable$。

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

55
56
58
60
17

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

1000000000000000000
Unreachable
1
Unreachable

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

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

提示

$2\leq N\leq2\times10 ^ 5$ $1\leq M\leq2\times10 ^ 5$ $1\leq l _ i,d _ i,k _ i,c _ i\leq10 ^ 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)$ 所有输入值均为整数。下图展示了该国运行的火车（省略了到达和出发时间的信息）。 考虑能够从车站 $2$ 到达车站 $6$ 的最晚时间。 如下面的图所示，可以在时间 $56$ 从车站 $2$ 出发，并按车站 $2\rightarrow$ 车站 $3\rightarrow$ 车站 $4\rightarrow$ 车站 $6$ 的顺序到达车站 $6$。 不可能在时间晚于 $56$ 从车站 $2$ 出发并到达车站 $6$，因此 $f(2)=56$。
存在一列在时间 $10 ^ {18}$ 从车站 $1$ 出发并在时间 $10 ^ {18}+10 ^ 9$ 到达车站 $5$ 的火车。此后没有从车站 $1$ 出发的火车，因此 $f(1)=10 ^ {18}$。 如上所示，答案可能无法装入 $32\operatorname{bit}$ 整数。 另外，第二条和第三条信息都保证存在一列在时间 $14$ 从车站 $2$ 出发并在时间 $20$ 到达车站 $3$ 的火车。 如上所示，某些火车可能在多条信息中出现。

标签: AtCoder|abc342E

来源

AtCoder|abc342E