結果
問題 |
No.2912 0次パーシステントホモロジー
|
ユーザー |
![]() |
提出日時 | 2024-10-04 22:06:32 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 462 ms / 2,000 ms |
コード長 | 1,335 bytes |
コンパイル時間 | 175 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 101,760 KB |
最終ジャッジ日時 | 2024-10-04 22:06:38 |
合計ジャッジ時間 | 4,387 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
from bisect import bisect_right class UnionFind: def __init__(self,n): self.n = n self.parent_size = [-1]*n def leader(self,a): if self.parent_size[a] < 0: return a self.parent_size[a] = self.leader(self.parent_size[a]) return self.parent_size[a] def merge(self,a,b): x, y = self.leader(a), self.leader(b) if x == y: return if abs(self.parent_size[x]) < abs(self.parent_size[y]): x, y = y, x self.parent_size[x] += self.parent_size[y] self.parent_size[y] = x return def same(self,a,b): return self.leader(a) == self.leader(b) def size(self,a): return abs(self.parent_size[self.leader(a)]) def groups(self): result = [[] for _ in range(self.n)] for i in range(self.n): result[self.leader(i)].append(i) return [r for r in result if r != []] N, M = map(int, input().split()) edge = [list(map(int, input().split())) for _ in range(M)] T = int(input()) R = list(map(int, input().split())) edge.sort(key=lambda x:x[2]) W = [] C = [N] cnt = N UF = UnionFind(N) for u, v, w in edge: if not UF.same(u, v): cnt -= 1 UF.merge(u, v) C.append(cnt) W.append(w) for r in R: print(C[bisect_right(W, r)])