Greedy Takahashi

题目描述

有 $N$ 个城市，编号为 $1$ 到 $N$，以及 $M$ 辆在这些城市之间行驶的巴士。第 $i$$(1 \leq i \leq M)$ 辆巴士在时间 $S_i+0.5$ 从城市 $A_i$ 出发并在时间 $T_i+0.5$ 到达城市 $B_i$。 Takahashi 将在这些 $N$ 个城市之间旅行。当他在时间 $t$ 位于城市 $p$ 时，他会执行以下操作。

如果存在一辆从城市 $p$ 出发且出发时间不早于时间 $t$ 的巴士，则乘坐在这些巴士中出发时间最早的一辆去往另一城市。 如果不存在这样的巴士，则不做任何事并停留在城市 $p$。

Takahashi 重复上述操作直到没有可乘坐的巴士为止。已保证所有 $M$ 辆巴士的出发时间两两不同，因此要乘坐的巴士总是唯一确定的。此外，换乘所需时间可以忽略不计。 任务如下：处理 $Q$ 个查询，第 $i$ 个查询 $(1 \leq i \leq Q)$ 如下。

如果 Takahashi 在时间 $X_i$ 开始在城市 $Y_i$ 出发，那么在时间 $Z_i$ 他会位于哪个城市或在哪辆巴士上？

输入格式

输入从标准输入按以下格式给出： $N$ $M$ $Q$ $A_1$ $B_1$ $S_1$ $T_1$ $A_2$ $B_2$ $S_2$ $T_2$ $\hspace{1.8cm}\vdots$ $A_M$ $B_M$ $S_M$ $T_M$ $X_1$ $Y_1$ $Z_1$ $X_2$ $Y_2$ $Z_2$ $\hspace{1.2cm}\vdots$ $X_Q$ $Y_Q$ $Z_Q$

输出格式

打印 $Q$ 行。第 $i$ 行应当包含第 $i$ 个查询的答案，格式如下。

如果 Takahashi 在时间 $Z_i$ 正在某辆巴士上，打印两个整数，表示该巴士的出发城市和到达城市，按此顺序并以空格分隔。 否则，即 Takahashi 在时间 $Z_i$ 位于某个城市，打印该城市的编号（一个整数）。

3 2 3
1 2 1 3
2 3 3 5
1 1 5
2 2 3
1 3 2

2 3
2
3

8 10 10
4 3 329982133 872113932
6 8 101082040 756263297
4 7 515073851 793074419
8 7 899017043 941751547
5 7 295510441 597348810
7 2 688716395 890599546
6 1 414221915 748470452
6 4 810915860 904512496
3 1 497469654 973509612
4 1 307142272 872178157
374358788 4 509276232
243448834 6 585993193
156350864 4 682491610
131643541 8 836902943
152874385 6 495945159
382276121 1 481368090
552433623 2 884584430
580376205 2 639442239
108790644 7 879874292
883275610 1 994982498

4
6 1
4 1
8
6 1
1
2
2
7 2
1

提示

$2 \leq N \leq 10^5$ $1 \leq M \leq 10^5$ $1 \leq Q \leq 10^5$ $1 \leq A_i,B_i \leq N\ (1 \leq i \leq M)$ $A_i \neq B_i\ (1 \leq i \leq M)$ $1 \leq S_i \lt T_i \leq 10^9\ (1 \leq i \leq M)$ $S_i \neq S_j\ (i \neq j)$ $1 \leq X_i \lt Z_i \leq 10^9\ (1 \leq i \leq Q)$ $1 \leq Y_i \leq N\ (1 \leq i \leq Q)$ 输入中的所有数值均为整数。在第一个查询中，Takahashi 的行程如下。

从时间 $1$ 在城市 $1$ 出发。 乘坐在时间 $1.5$ 从城市 $1$ 出发并在时间 $3.5$ 到达城市 $2$ 的巴士。 乘坐在时间 $3.5$ 从城市 $2$ 出发并在时间 $5.5$ 到达城市 $3$ 的巴士。 由于不存在在时间 $5.5$ 或之后从城市 $3$ 出发的巴士，停留在城市 $3$（永远）。

在时间 $5$，他会在从城市 $2$ 出发并前往城市 $3$ 的巴士上。因此，如输出部分所述，我们应该打印 $2$ 和 $3$，中间以空格分隔。

标签: AtCoder|abc212F

来源

AtCoder|abc212F