比赛场次 658
比赛名称 板子大赛
比赛状态 已结束比赛成绩
开始时间 2025-01-22 08:00:00
结束时间 2025-01-22 17:00:00
开放分组 全部用户
组织者 syzhaoss
注释介绍 都是板子,AK吧!
题目名称 社交网络
输入输出 relation.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
GravatarAeeE5x AAAAAAAAAA 0.224 s 3.42 MiB 100
Gravatarzqy AAAAAAAAAA 0.225 s 3.45 MiB 100
Gravatarduck AAAAAAAAAA 0.231 s 3.43 MiB 100
Gravatarzhm AAAAAAAAAA 0.232 s 1.42 MiB 100
Gravatar长安惊龙灵松 AAAAAAAAAA 0.237 s 3.42 MiB 100
GravatarIMZ AAAAAAAAAA 0.246 s 3.43 MiB 100
Gravatarxxz AAAAAAAAAA 0.254 s 3.44 MiB 100
Gravatar对立猫猫对立 AAAAAAAAAA 1.136 s 3.40 MiB 100
Gravatar秋_Water AAAAAAAAAA 1.143 s 3.32 MiB 100
GravatarChenBp AAAAAAAAAA 1.245 s 3.30 MiB 100
Gravatar李奇文 AAAAAAAAAA 1.697 s 3.34 MiB 100

18. 社交网络

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

【题目背景】

你知道吗?你和任何一个陌生人之间所间隔的人不会超六个,也就是说,最多通过六个人你就能够认识任何一个陌生人。

【题目描述】

现在给定 $n$ 个人,假设这 $n$ 个人开始时互相都不认识,现在逐步令他们直接互相认识,当然中间也会询问是两个人是否能有联系。

【输入格式】

第一行两个整数 $n,m$,表示总共有 $n$ 个人,有 $m$ 次操作。

接下来 $m$ 行,每行三个整数 $op, x, y$。

若 $op=0$,则说明 $x$ 和 $y$ 之间直接认识。

若 $op=1$,根据当前已知的关系,询问 $x$ 和 $y$ 是否有联系。

【输出格式】

对于每个询问,若 $x$ 和 $y$ 有联系,则输出Yes,否则输出No

【样例输入】

9 10
0 2 4
0 5 7
0 1 3
0 1 2
1 3 4
0 8 9
0 5 6
1 8 5
0 2 3
1 7 6

【样例输出】

Yes
No
Yes

【数据范围与约定】

对于$30\%$的数据,有$n\leq 100,m\leq 2000$。

对于$100\%$的数据,有$n\leq 2\times 10^4,m\leq 10^5$。