AT_agc031_f.[AGC031F] Walk on Graph

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

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

题目描述

给定一个有 $N$ 个顶点、 $M$ 条边的连通无向图。每个顶点编号为 $1,2,\ldots,N$ 。第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$ ，边长为 $C_i$ 。此外，给定一个奇数 $MOD$ 。

有 $Q$ 个查询，每个查询的格式如下：

第 $i$ 个查询给出 $S_i,T_i,R_i$ 。请判断是否存在一条从顶点 $S_i$ 到顶点 $T_i$ 的路径，使得该路径的长度模 $MOD$ 后的余数为 $R_i$ 。这里允许多次经过同一条边，也允许刚走过的边立即返回。

但在本题中，路径的长度不是边长的简单和，而是第 $1$ 条经过的边的长度乘以 $1$ ，第 $2$ 条经过的边的长度乘以 $2$ ，第 $3$ 条经过的边的长度乘以 $4$ ，以此类推。更严格地说，若依次经过长度为 $L_1,\ldots,L_k$ 的边，则该路径的长度为 $\sum L_i \times 2^{i-1}$ 。

输入格式

输入按以下格式从标准输入读入。

$N$ $M$ $Q$ $MOD$
$A_1$ $B_1$ $C_1$
$\vdots$
$A_M$ $B_M$ $C_M$
$S_1$ $T_1$ $R_1$
$\vdots$
$S_Q$ $T_Q$ $R_Q$

输出格式

对于每个查询，第 $i$ 行输出该查询的答案。

输入输出样例

输入#1

输出#1

YES
NO

输入#2

输出#2

YES
NO
NO

输入#3

输出#3

YES
YES
YES

输入#4

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

输出#4

YES
NO
NO
NO
NO
NO
NO
YES
YES
NO

说明/提示

数据范围

$1 \leq N, M, Q \leq 50000$
$3 \leq MOD \leq 10^6$
$MOD$ 是奇数
$1 \leq A_i, B_i \leq N$
$0 \leq C_i \leq MOD-1$
$1 \leq S_i, T_i \leq N$
$0 \leq R_i \leq MOD-1$
给定的图是连通的（但可能有自环和重边）

样例解释 1

各个查询的答案如下：

第 $1$ 个查询：按 $1,2,3$ 的顺序前进，路径长度为 $1 \times 2^0 + 2 \times 2^1 = 5$ ，存在一条长度模 $2019$ 余 $5$ 的路径，所以答案为 YES。
第 $2$ 个查询：无论如何从顶点 $1$ 到顶点 $3$ ，路径长度模 $2019$ 都不可能为 $4$ ，所以答案为 NO。

由 ChatGPT 4.1 翻译

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

首页