【ZYCode R2】并查集
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目背景
看到 SPFA 出题团的 Ex 题,灵机一动,出出来了这题
题目描述
给定一个长度为 \(n\) 的 \(a\) 数列,第 \(i\) 个数一开始等于 \(i\), 并可以与它距离 \(p_i\) 以内的数交换,问经过无数次交换后,\(a\) 数列是否能变成 \(b\) 数列?
\(t\) 组测试数据
输入格式
第一行一个数 \(t\)
接下来三行为一组
第一行一个数 \(n\)
第二行 \(n\) 个数,第 \(i\) 个数代表 \(p_i\)
第三行 \(n\) 个数,代表 \(b\) 数列,数据保证 \(b\) 数列也是 \(1\) 到 \(n\) 的全排列
输出格式
Yes
或 No
样例
样例输入 1
1
5
1 1 1 1 1
5 4 3 2 1
样例输出 1
Yes
样例输入 2
1
5
1 0 0 0 1
5 4 3 2 1
样例输出 2
No
提示说明
在样例1
中,每个数都可以和其相邻的数交换,可以达成 \(b\) 数列。
在样例2
中,除了3
,其它数都不能换到它们应该到的位置
对于 \(30\%\) 的数据
\( 1 \le n \le 1000 \)
对于另外 \(30\%\) 的数据
\( 1 \le p \le 10 \)
对于\(100\%\) 的数据
\( t \le 10 \)
\( 1 \le p \le n \le 10^5\)
ZYCode Normal Round #2
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 5
- 开始于
- 2023-05-12 20:45
- 结束于
- 2023-05-12 20:51
- 持续时间
- 0.1 小时
- 主持人
- 参赛人数
- 3