比赛场次 613
比赛名称 2024暑期C班集训3
比赛状态 已结束比赛成绩
开始时间 2024-07-03 08:15:00
结束时间 2024-07-03 12:00:00
开放分组 全部用户
注释介绍 都什么年代还在打传统模拟赛?
https://www.luogu.com.cn/paste/dlzue89u
题目名称 不是一道路径查询问题
输入输出 Paths.in/out
时间限制 1000 ms (1 s)
内存限制 512 MiB
测试点数 20 简单对比
用户 结果 时间 内存 得分
GravatardarkMoon AAAAAAAAAAAAAAAAAAAA
2.835 s 12.98 MiB 100
Gravatar┭┮﹏┭┮ AAAAAAAAAAAAAAEWEEEE
1.567 s 14.44 MiB 70
Gravatar小金 AAAAAAAAAAAAEEEEEEEE
1.428 s 11.51 MiB 60
Gravatar健康铀 AAAWAAAAAAAAWWWATTTT
5.982 s 11.75 MiB 60
GravatarUntitled AAAAAAAAAAAATTTTTTTT
9.067 s 18.14 MiB 60
Gravatarwzh0425 AWAAAAAAAAAAEEEEEEEE
2.002 s 118.11 MiB 55
Gravatarliuyiche AAAAAAAAATAATTTTTTTT
9.599 s 11.28 MiB 55
Gravatardjyqjy AAAAAAAAAEAEEEETTTTT
8.852 s 11.46 MiB 50
Gravatar123 AAAAAAAATTTTTTTTTTTT
12.210 s 22.95 MiB 40
Gravatar彭欣越 WWWWWWAATTTTTTEEEEEE
8.591 s 11.41 MiB 10
GravatarAeeE5x RRRRRRRRRRRRRRRRRRRR
0.027 s 12.60 MiB 0
Gravatarflyfree WWWWWWWWWWWWEEEEEEEE
1.459 s 5.39 MiB 0

不是一道路径查询问题

★   输入文件:Paths.in   输出文件:Paths.out   简单对比
时间限制:1 s   内存限制:512 MiB

【题目背景】

都什么年代了还在做传统路径查询问题?

【题目描述】

在阅读《Distributed Exact Shortest Paths in Sublinear Time》这篇论文后,您学会了如何在 $\mathcal{O}(D^{1/3} \cdot (n \log n)^{2/3})$ 的复杂度内解决分布式单源最短路问题。为了测试您是否真的学有所成,小青鱼为您准备了如下问题。

小青鱼有一张包含 $n$ 个节点与 $m$ 条无向边的图,节点编号从 $1$ 到 $n$。第 $i$ 条边连接节点 $u_i$ 和 $v_i$,边权为 $w_i$。

对于任意一条连接节点 $u$ 和 $v$ 的路径,定义路径的价值为路径上所有边的边权进行按位与(bitwise AND)计算的结果。

小青鱼很喜欢高价值的路径,因此他设定了一个固定的阈值 $V$。称小青鱼喜爱一条路径,当且仅当这条路径的价值至少为 $V$。

接下来,小青鱼将会提出 $q$ 次询问,第 $i$ 次询问可以用一对整数 $(u_i, v_i)$ 表示。对于每次询问,您需要判断节点 $u_i$ 到 $v_i$ 是否存在一条小青鱼喜爱的路径。

【输入格式】

第一行输入四个整数 $n$,$m$,$q$ 和 $V$($1 \le n \le 10^5$,$0 \le m \le 5 \times 10^5$,$1 \leq q \leq 5 \times 10^5$,$0 \leq V < 2^{60}$)表示图中的节点数以及边数,小青鱼的询问数以及固定阈值。

对于接下来 $m$ 行,第 $i$ 行输入三个整数 $u_i$,$v_i$ 和 $w_i$($1 \le u_i,v_i \le n$,$u_i \ne v_i$,$0 \leq w_i < 2^{60}$)表示一条连接节点 $u_i$ 和 $v_i$ 的无向边,边权为 $w_i$。两个节点之间可能存在多条边。

对于接下来 $q$ 行,第 $i$ 行输入两个整数 $u_i$ 和 $v_i$($1 \leq u_i, v_i \leq n$,$u_i \ne v_i$)表示一次询问。

【输出格式】

每次询问输出一行。若节点 $u_i$ 和 $v_i$ 之间存在一条价值至少为 $V$ 的路径输出 `Yes`,否则输出 `No`。

【样例输入】

9 8 4 5
1 2 8
1 3 7
2 4 1
3 4 14
2 5 9
4 5 7
5 6 6
3 7 15
1 6
2 7
7 6
1 8

【样例输出】

Yes
No
Yes
No

【样例说明】

- 对于第一次询问,一条合法的路径为 $1 \to 3 \to 4 \to 5 \to 6$,其价值为 $7 \,\&\, 14 \,\&\, 7 \,\&\, 6 = 6 \ge 5$。

- 对于第三次询问,一条合法的路径为 $7 \to 3 \to 4 \to 5 \to 6$,其价值为 $15 \,\&\, 14 \,\&\, 7 \,\&\, 6  = 6 \ge 5$。

- 对于第四次询问,因为节点 $1$ 与 $8$ 之间不存在任何路径,因此答案为 `No`。

【数据规模与约定】

大样例

对于 $100\%$ 的数据:$1 \le n \le 10^5, 0 \le m \le 5 \times 10^5, 1 \leq q \leq 5 \times 10^5, 0 \leq V,w_i < 2^{60}$。

·$Subtask1(40pts): n,m\le 10$。

·$Subtask2(20pts): n,m,q\le 100,V\lt 2^6$。

·$Subtask3(40pts): 无特殊限制$。

【来源】

[SDCPC2023] Not Another Path Query Problem。