結果
問題 | No.1779 Magical Swap |
ユーザー |
|
提出日時 | 2022-01-26 06:00:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 346 ms / 2,000 ms |
コード長 | 2,832 bytes |
コンパイル時間 | 205 ms |
コンパイル使用メモリ | 82,476 KB |
実行使用メモリ | 102,352 KB |
最終ジャッジ日時 | 2024-12-21 07:52:35 |
合計ジャッジ時間 | 5,542 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 18 |
ソースコード
class UnionFind:def __init__(self, n):self.n = nself.parents = [-1] * ndef find(self, x):""" 根を見つける関数を定義(同時にxを直接根にくっつける操作も行う)"""tmp = []parents = self.parentswhile parents[x] >= 0:tmp.append(x)x = parents[x]for y in tmp:parents[y] = xreturn xdef union(self, x, y):""" 二つの木をくっつける(子を多く持つ方を根とした親子関係)。これは破壊的操作を行う。"""x = self.find(x)y = self.find(y)if x == y:returnif self.parents[x] > self.parents[y]:x, y = y, xself.parents[x] += self.parents[y]self.parents[y] = xdef same(self, x, y):""" xとyが同じ根の子かを判定 """return self.find(x) == self.find(y)def size(self, x):""" xの根のparent(= 要素数)を返す """return -self.parents[self.find(x)]def members(self, x):""" xが属するグループの要素をリストとして返す O(N)"""root = self.find(x)return [i for i in range(self.n) if self.find(i) == root]def roots(self):""" 全ての根の要素をリストとして返す O(N)"""return [i for i, x in enumerate(self.parents) if x < 0]def group_count(self):""" グループの数を返す O(N)"""return len(self.roots())def size_list(self):""" 各グループの要素数のリストを返す(根の番号は返さない) O(N)"""return [-x for x in self.parents if x < 0]def all_group_members(self):""" {根:[根の子(根を含む)のリスト],...}を辞書で返す O(N)"""res = [[] for _ in range(self.n)]for i in range(self.n):x = self.find(i)res[x].append(i)return {r: res[r] for r in self.roots()}def __str__(self):return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())##############################################################################################################import sysinput = sys.stdin.readlineT=int(input())for _ in range(T):N=int(input())A=list(map(int, input().split()))B=list(map(int, input().split()))U = UnionFind(N)for k in range(2,N+1):for i in range(1,N+1):if (i+1)*k>N:breakU.union(i*k-1,(i+1)*k-1)for _,p in U.all_group_members().items():AA=[]BB=[]for i in p:AA.append(A[i])BB.append(B[i])AA.sort()BB.sort()if AA!=BB:print("No")breakelse:print("Yes")