题目详情题解（0）讨论（0）提交记录（0）

AT_agc012_b.[AGC012B] Splatter Painting

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

イカ喜欢给图的顶点涂色。

给定一个由 NN 个编号为 11 至 NN 的顶点和 MM 条边组成的简单无向图。所有顶点初始时都被涂有颜色 00。第 ii 条边连接顶点 aia_i 与顶点 bib_i，边的长度为 11，且是双向的。

イカ对这张图进行了 QQ 次操作。在第 ii 次操作时，将距离顶点 viv_i 不超过 did_i 的所有顶点的颜色覆盖为颜色 cic_i。

请在 QQ 次操作结束后，输出每个顶点被涂的颜色。

输入格式

输入以以下形式从标准输入中给出。

NN MM
a1a_1 b1b_1
⋮\vdots
aMa_M bMb_M
QQ
v1v_1 d1d_1 c1c_1
⋮\vdots
vQv_Q dQd_Q cQc_Q

输出格式

输出 NN 行。第 ii 行输出第 ii 个顶点在所有操作后的颜色。

输入输出样例

  • 输入#1

    7 7
1 2
1 3
1 4
4 5
5 6
5 7
2 3
2
6 1 1
1 2 2

    输出#1

    2
2
2
2
2
1
0

  • 输入#2

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

    输出#2

    1
0
3
1
5
5
3
3
6
1
3
4
5
3

说明/提示

条件限制

  • 1≤N,M,Q≤1051 \leq N, M, Q \leq 10^5
  • 1≤ai,bi,vi≤N1 \leq a_i, b_i, v_i \leq N
  • ai≠bia_i \neq b_i
  • 0≤di≤100 \leq d_i \leq 10
  • 1≤ci≤1051 \leq c_i \leq 10^5
  • did_i 与 cic_i 都是整数
  • 输入的图中不存在自环和重边

部分得分

  • 若能通过满足 1≤N,M,Q≤2,0001 \leq N, M, Q \leq 2{,}000 的数据集，可获得 200200 分的部分分数。

样例解释 1

初始时，每个顶点的颜色为 00。经过第 11 次操作后，顶点 5,65,6 的颜色被覆盖为 11。第 22 次操作后，顶点 1,2,3,4,51,2,3,4,5 的颜色被覆盖为 22。

样例1说明图片

样例解释 2

给定的图不一定是连通的。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页