結果
問題 | No.2316 Freight Train |
ユーザー |
|
提出日時 | 2023-05-26 21:57:01 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 881 ms / 2,000 ms |
コード長 | 1,519 bytes |
コンパイル時間 | 514 ms |
コンパイル使用メモリ | 82,524 KB |
実行使用メモリ | 108,288 KB |
最終ジャッジ日時 | 2024-12-25 06:42:37 |
合計ジャッジ時間 | 20,485 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
class DisjointSetUnion():def __init__(self, n):self.n = nself.par_or_size = [-1] * ndef merge(self, a, b):assert(0 <= a < self.n)assert(0 <= b < self.n)la = self.leader(a)lb = self.leader(b)if la == lb:return laif -self.par_or_size[la] < -self.par_or_size[lb]:la, lb = lb, laself.par_or_size[la] += self.par_or_size[lb]self.par_or_size[lb] = lareturn ladef same(self, a, b):assert(0 <= a < self.n)assert(0 <= b < self.n)return self.leader(a) == self.leader(b)def leader(self, a):assert(0 <= a < self.n)if (self.par_or_size[a] < 0):return aelse:self.par_or_size[a] = self.leader(self.par_or_size[a])return self.par_or_size[a]def size(self, a):assert(0 <= a < self.n)return - self.par_or_size[self.leader(a)]def group(self):result = dict()for a in range(self.n):la = self.leader(a)if la not in result:result[la] = []result[la].append(a)return resultN, Q = map(int, input().split())dsu = DisjointSetUnion(N)P = list(map(int, input().split()))for i in range(N):if P[i] != -1:dsu.merge(i, P[i] - 1)for i in range(Q):a, b = map(int, input().split())if dsu.same(a - 1, b - 1):print("Yes")else:print("No")