#P11986. [JOIST 2025] 救护车 / Ambulance

[JOIST 2025] 救护车 / Ambulance

题目背景

由于评测机性能差距,本题增加 1 秒时限。

题目描述

IOI 王国被表示为一个 LLLL 列的方形网格。行从上到下编号为 1,2,,L1, 2, \dots, L,列从左到右编号为 1,2,,L1, 2, \dots, L

位于第 ii 行(1iL1 \leq i \leq L)和第 jj 列(1jL1 \leq j \leq L)的单元格记为 (i,j)(i, j)

由于近期疫情扩散,国王比太郎决定在网格的四个角落(单元格 (1,1)(1, 1)(1,L)(1, L)(L,1)(L, 1)(L,L)(L, L))各建造一所医院,每所医院配备一辆救护车。救护车运输规则如下:

  • 救护车可在时间 00 或之后开始移动。
  • 救护车会重复以下步骤(可能 00 次):
    • 从所属医院出发 \to 移动到患者位置 \to 接载患者 \to 返回医院并放下患者。
  • 每辆救护车一次最多运送 11 名患者。
  • 救护车只能将患者送回其初始所属医院,不可在其他位置放下患者
  • 救护车每次移动到四连通单元格(上下左右)耗时 11 单位时间。接载和放下患者的耗时忽略。
  • 不同医院的救护车可同时占据同一单元格。

已知第 kk 名患者位于 (Xk,Yk)(X_k, Y_k),判断是否所有患者都能在时间 TT 内被运送到任意医院。

输入格式

如下所示:

LL NN TT
X1X_1 Y1Y_1
X2X_2 Y2Y_2
\vdots
XNX_N YNY_N

输出格式

若所有患者可在时间 TT 内被送医,输出 Yes\texttt{Yes}

否则输出 No\texttt{No}

6 4 8
1 3
2 2
3 4
5 5
Yes
9 5 19
5 5
5 5
7 5
2 5
9 5
No
7 7 16
6 1
2 4
4 5
5 5
3 4
6 4
5 1
Yes
200 15 800
126 45
196 40
43 58
96 13
28 33
44 55
60 22
58 156
135 183
44 29
92 182
157 138
30 132
175 87
166 57
No

提示

样例解释

样例 11 解释

  • 将第 11 和第 22 个病人送往位于 (1,1)(1, 1) 的医院;
  • 将第 33 个病人送往位于 (1,6)(1, 6) 的医院;
  • 将第 44 个病人送往位于 (6,6)(6, 6) 的医院。

这样,所有病人都可以在第 88 个时间点被送往医院,因此输出 Yes\texttt{Yes}

例如,如果停靠在 (1,1)(1, 1) 医院的救护车按照以下顺序移动,它可以在第 88 个时间点之前将第 11 和第 22 个病人都送到医院。

时间 救护车状态
00 从单元格 (1,1)(1, 1) 出发
11 到达单元格 (2,1)(2, 1)
22 到达单元格 (2,2)(2, 2),接上第 2 个病人,出发
33 到达单元格 (1,2)(1, 2)
44 到达单元格 (1,1)(1, 1),放下第 2 个病人,出发
55 到达单元格 (1,2)(1, 2)
66 到达单元格 (1,3)(1, 3),接上第 1 个病人,出发
77 到达单元格 (1,2)(1, 2)
88 到达单元格 (1,1)(1, 1),放下第 1 个病人

该样例满足子任务 14,6,71\sim 4,6,7 的限制。

样例 22 解释

可以证明不可能做到,所以输出 No\texttt{No}

该样例满足所有子任务的限制。

样例 33 解释

该样例满足子任务 14,6,71\sim 4,6,7 的限制。

样例 44 解释

该样例满足子任务 4,6,74,6,7 的限制。

数据范围

  • 3L100003 \leq L \leq 10\,000
  • 1N1601 \leq N \leq 160
  • 1T200001 \leq T \leq 20\,000
  • 1Xk,YkL1 \leq X_k, Y_k \leq L
  • (Xk,Yk)(X_k, Y_k) 不与 (1,1),(1,L),(L,1),(L,L)(1, 1), (1, L), (L, 1), (L, L) 的任意一个相等;
  • 所有输入值为整数。

子任务

子任务 分数 特殊性质
11 44 T50T \leq 50
22 88 T160T \leq 160
33 55 N10N \leq 10
44 1818 N20N \leq 20
55 1515 N45N \leq 45LL 为奇数,且所有患者满足 Yk=L+12Y_k = \frac{L+1}{2}
66 3131 N45N \leq 45
77 1919 /