[JOIST 2024] 棋盘游戏 / Board Game

Luogu

IDLGP10433

Time4000ms

Memory1024MB

DifficultyP7

图论2024最短路凸包Ad-hoc根号分治JOISC/JOIST（日本）

有一个供 $K$ 个玩家玩的棋盘游戏。该游戏的棋盘由 $N$ 个编号从 1 到 $N$ 的单元格和 $M$ 条编号从 1 到 $M$ 的路径组成，其中路径 $j$（$1 ≤ j ≤ M$）双向连接着单元格 $U_j$ 和 $V_j$。棋盘上有两种类型的单元格：重新激活单元格和停止单元格。这些信息由长度为 $N$ 的字符串 $S$ 给出，$S$ 由 $0$ 和 $1$ 组成，其中 $S$ 的第 $i$ 个字符（$1 ≤ i ≤ N$）是 '0' 表示单元格 $i$ 是重新激活单元格，是 '1' 表示单元格 $i$ 是停止单元格。这个棋盘游戏由编号从 $1$ 到 $K$ 的 $K$ 个玩家进行。每个玩家都有自己的棋子，游戏从每个玩家将其棋子放在特定的单元格上开始。一开始，玩家 $p$（$1 \leq p \leq K$）将其棋子放在单元格 $X_p$ 上。注意，多个玩家的棋子可以放在同一个单元格上。游戏随着每个玩家轮流进行而进行，从玩家 1 开始，按数字顺序进行。在玩家 $p$ 完成其回合后，玩家 $p + 1$ 开始回合（如果 $p = K$，则玩家 1 开始回合）。每个玩家在其回合上执行以下操作： 1. 选择与其棋子所在的单元格通过一条路径相连的一个单元格，并将其棋子移动到所选择的单元格上。 2. 如果目标单元格是重新激活单元格，则重复步骤 1 并继续其回合。如果目标单元格是停止单元格，则结束其回合。代表日本参加这个棋盘游戏的包括 JOI 君在内的由 $K$ 名成员组成的团队，正在研究协作策略，以快速征服这个游戏。他们目前正在研究以下问题：为了将玩家 1 的棋子放置在单元格 $T$ 上，$K$ 名玩家需要的最小总移动次数是多少？即使在回合中途，如果玩家 1 的棋子被放置在单元格 $T$ 上，也认为满足条件。给定关于游戏棋盘和每个玩家棋子的初始放置位置的信息，编写一个程序来计算每个 $T = 1, 2, \ldots, N$ 对应的问题的答案。 ## Input 从标准输入中读取以下数据： - $N$ $M$ $K$ - $U_1$ $V_1$ - $U_2$ $V_2$ - ... - $U_M$ $V_M$ - $S$ - $X_1,X_2,...,X_K$ ## Output 输出 $N$ 行。在第 $T$ 行（$1 ≤ T ≤ N$）上，输出 $K$ 个玩家将玩家 1 的棋子放在单元格 $T$ 上所需的最小总移动次数。 [samples] ## Note #### 样例解释 1 由于玩家 $1$ 的棋子从单元格 $1$ 开始，所以 $T = 1$ 的答案是 $0$。对于 $T = 2$，在第一步中，玩家 $1$ 可以将他的棋子从单元格 $1$ 移动到单元格 $2$。因此，$T = 2$ 的答案是 $1$。对于 $T = 3$，他们可以通过以下 $2$ 步将玩家 $1$ 的棋子放置在单元格 $3$ 上： - 在第一步中，玩家 $1$ 将他的棋子从单元格 $1$ 移动到单元格 $2$。由于单元格 $2$ 是一个激活单元格，因此玩家 $1$ 的回合继续。 - 在第二步中，玩家 $1$ 将他的棋子从单元格 $2$ 移动到单元格 $3$。由于他们无法在 $1$ 步或更少的步骤中将玩家 $1$ 的棋子放置在单元格 $3$ 上，所以 $T = 3$ 的答案是 $2$。类似地，可以验证 $T = 4$ 的答案为 $2$，$T = 5$ 的答案为 $3$。这个样例输入满足子任务 $1,4,5,6,7,8$ 的约束。 #### 样例解释 2 对于 $T = 3$，他们可以通过以下 4 步将玩家 $1$ 的棋子放置在单元格 $3$ 上： - 在第一步中，玩家 $1$ 将他的棋子从单元格 $1$ 移动到单元格 $2$。由于单元格 $2$ 是一个停止单元格，接下来轮到玩家 $2$。 - 在第二步中，玩家 $2$ 将他的棋子从单元格 $5$ 移动到单元格 $3$。由于单元格 $3$ 是一个激活单元格，玩家 $2$ 的回合继续。 - 在第三步中，玩家 $2$ 将他的棋子从单元格 $3$ 移动到单元格 $2$。由于单元格 $2$ 是一个停止单元格，接下来轮到玩家 $1$。 - 在第四步中，玩家 $1$ 将他的棋子从单元格 $2$ 移动到单元格 $3$。由于他们无法在 $3$ 步或更少的步骤中将玩家 $1$ 的棋子放置在单元格 $3$ 上，所以 $T = 3$ 的答案是 $4$。这个样例输入满足子任务 $2,4,5,6,7,8$ 的约束。 #### 样例解释 3 这个样例输入满足子任务 $3, 4, 5, 6, 7,8$ 的约束。 #### 样例解释 4 这个样例输入满足子任务 $4, 6, 7,8$ 的约束。 #### 样例解释 5 这个样例输入满足子任务 $4, 6, 7,8$ 的约束。 ### 约束条件 - $2 \leq N \leq 50,000$ - $1 \leq M \leq 50,000$ - $2 \leq K \leq 50,000$ - $1 \leq U_j < V_j \leq N$（$1 \leq j \leq M$） - $(U_j, V_j)$，$(U_k, V_k)$（$1 \leq j < k \leq M$） - 可以通过经过多条路径从任何单元格到达任何其他单元格。 - $S$ 是长度为 $N$ 的由 '0' 和 '1' 组成的字符串。 - $1 \leq X_p \leq N$（$1 \leq p \leq K$） - $N$、$M$ 和 $K$ 都是整数。 - $U_j$ 和 $V_j$ 是整数（$1 \leq j \leq M$）。 - $X_p$ 是整数（$1 \leq p \leq K$）。 ### 子任务 1. (3 分) 没有终止单元格。 2. (7 分) 恰好有一个终止单元格。 3. (7 分) 恰好有两个终止单元格。 4. (19 分) $N \leq 3,000$，$M \leq 3,000$，$K \leq 3,000$ 5. (23 分) $K = 2$ 6. (9 分) $K \leq 100$ 7. (23 分) $N \leq 30,000$，$M \leq 30,000$，$K \leq 30,000$ 8. (9 分) 没有额外的约束。

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

Input #4

Output #4

Input #5

12 13 3
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 10
2 9
7 12
11 12
110000011101
1 9 11

Output #5

API Response (JSON)

{
  "problem": {
    "name": "[JOIST 2024] 棋盘游戏 / Board Game",
    "description": {
      "content": "有一个供 $K$ 个玩家玩的棋盘游戏。该游戏的棋盘由 $N$ 个编号从 1 到 $N$ 的单元格和 $M$ 条编号从 1 到 $M$ 的路径组成，其中路径 $j$（$1 ≤ j ≤ M$）双向连接着单元格 $U_j$ 和 $V_j$。 棋盘上有两种类型的单元格：重新激活单元格和停止单元格。 这些信息由长度为 $N$ 的字符串 $S$ 给出，$S$ 由 $0$ 和 $1$ 组成，其中 $S$ 的",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10433"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有一个供 $K$ 个玩家玩的棋盘游戏。该游戏的棋盘由 $N$ 个编号从 1 到 $N$ 的单元格和 $M$ 条编号从 1 到 $M$ 的路径组成，其中路径 $j$（$1 ≤ j ≤ M$）双向连接着单元格 $U_j$ 和 $V_j$。\n\n棋盘上有两种类型的单元格：重新激活单元格和停止单元格。\n\n这些信息由长度为 $N$ 的字符串 $S$ 给出，$S$ 由 $0$ 和 $1$ 组成，其中 $S$ 的...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments