結果
問題 | No.2316 Freight Train |
ユーザー |
|
提出日時 | 2023-05-26 22:32:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,203 ms / 2,000 ms |
コード長 | 1,403 bytes |
コンパイル時間 | 187 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 264,992 KB |
最終ジャッジ日時 | 2024-12-25 08:34:16 |
合計ジャッジ時間 | 21,677 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
import sys sys.setrecursionlimit(10 ** 9) class UnionFind: def __init__(self, n): self.parents = [-1] * n self.list_of_size = [1] * n def find_root(self, x): if self.parents[x] < 0: return x else: self.parents[x] = self.find_root(self.parents[x]) return self.parents[x] def union(self, x, y): root_of_x = self.find_root(x) root_of_y = self.find_root(y) if root_of_x == root_of_y: return if self.parents[root_of_x] > self.parents[root_of_y]: self.parents[root_of_x] = root_of_y self.list_of_size[y] += self.list_of_size[x] else: self.parents[root_of_y] = root_of_x self.list_of_size[x] += self.list_of_size[y] if self.parents[root_of_x] == self.parents[root_of_y]: self.parents[root_of_x] -= 1 def same(self, x, y): return self.find_root(x) == self.find_root(y) def size(self, x): return self.list_of_size[self.find_root(x)] N, Q = map(int, input().split()) P = list(map(int, input().split())) uf = UnionFind(N) for i in range(N): if P[i] == -1: continue uf.union(i, P[i]-1) for j in range(Q): A, B = map(int, input().split()) A -= 1 B -= 1 if uf.same(A, B): print("Yes") else: print("No")