【ZYCode R2】并查集

【ZYCode R2】并查集

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

看到 SPFA 出题团的 Ex 题,灵机一动,出出来了这题

题目描述

给定一个长度为 \(n\) 的 \(a\) 数列,第 \(i\) 个数一开始等于 \(i\), 并可以与它距离 \(p_i\) 以内的数交换,问经过无数次交换后,\(a\) 数列是否能变成 \(b\) 数列?

\(t\) 组测试数据

输入格式

第一行一个数 \(t\)

接下来三行为一组

第一行一个数 \(n\)

第二行 \(n\) 个数,第 \(i\) 个数代表 \(p_i\)

第三行 \(n\) 个数,代表 \(b\) 数列,数据保证 \(b\) 数列也是 \(1\) 到 \(n\) 的全排列

输出格式

YesNo

样例

样例输入 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