結果
問題 |
No.317 辺の追加
|
ユーザー |
![]() |
提出日時 | 2025-03-26 15:46:27 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 530 ms / 2,000 ms |
コード長 | 1,973 bytes |
コンパイル時間 | 241 ms |
コンパイル使用メモリ | 82,308 KB |
実行使用メモリ | 126,888 KB |
最終ジャッジ日時 | 2025-03-26 15:47:02 |
合計ジャッジ時間 | 13,852 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
import sys from collections import defaultdict class UnionFind: def __init__(self, size): self.parent = list(range(size + 1)) # 1-based indexing self.size = [1] * (size + 1) def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): x_root = self.find(x) y_root = self.find(y) if x_root == y_root: return if self.size[x_root] < self.size[y_root]: x_root, y_root = y_root, x_root self.parent[y_root] = x_root self.size[x_root] += self.size[y_root] def main(): input = sys.stdin.read().split() idx = 0 N = int(input[idx]) idx += 1 M = int(input[idx]) idx += 1 uf = UnionFind(N) for _ in range(M): u = int(input[idx]) idx += 1 v = int(input[idx]) idx += 1 uf.union(u, v) size_count = defaultdict(int) has_size = [False] * (N + 1) for i in range(1, N + 1): if uf.find(i) == i: s = uf.size[i] size_count[s] += 1 has_size[s] = True sizes = sorted(size_count.keys(), reverse=True) INF = N + 1 dp = [INF] * (N + 1) dp[0] = 0 for s in sizes: max_count = size_count[s] k = 1 while max_count > 0: take = min(k, max_count) a = take max_count -= take k *= 2 current_s = s * a for j in range(N, -1, -1): if dp[j] != INF and j + current_s <= N: if dp[j + current_s] > dp[j] + a: dp[j + current_s] = dp[j] + a for i in range(1, N + 1): if has_size[i]: print(0) else: if dp[i] < INF: print(dp[i] - 1) else: print(-1) if __name__ == "__main__": main()