結果
問題 | No.1293 2種類の道路 |
ユーザー |
![]() |
提出日時 | 2020-11-20 22:26:55 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 309 ms / 2,000 ms |
コード長 | 1,470 bytes |
コンパイル時間 | 272 ms |
コンパイル使用メモリ | 82,472 KB |
実行使用メモリ | 96,172 KB |
最終ジャッジ日時 | 2024-07-23 13:20:25 |
合計ジャッジ時間 | 5,367 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
import sysinput = lambda: sys.stdin.readline().rstrip()class UnionFind():def __init__(self, n):self.n = nself.PA = [-1] * ndef root(self, a):L = []while self.PA[a] >= 0:L.append(a)a = self.PA[a]for l in L:self.PA[l] = areturn adef unite(self, a, b):ra, rb = self.root(a), self.root(b)if ra != rb:if self.PA[rb] >= self.PA[ra]:self.PA[ra] += self.PA[rb]self.PA[rb] = raelse:self.PA[rb] += self.PA[ra]self.PA[ra] = rbdef size(self, a):return -self.PA[self.root(a)]def groups(self):G = [[] for _ in range(self.n)]for i in range(self.n):G[self.root(i)].append(i)return [g for g in G if g]def group_size(self):G = [[] for _ in range(self.n)]for i in range(self.n):G[self.root(i)].append(i)return [len(g) for g in G if g]N, D, W = map(int, input().split())uf1 = UnionFind(N)uf2 = UnionFind(N)for _ in range(D):a, b = map(int, input().split())uf1.unite(a-1, b-1)for _ in range(W):a, b = map(int, input().split())uf2.unite(a-1, b-1)ans = -Nfor g in uf1.groups():s = len(g)S = set()for a in g:r = uf2.root(a)if r not in S:S.add(r)ans += uf2.size(r) * sprint(ans)