結果
問題 | No.1293 2種類の道路 |
ユーザー |
|
提出日時 | 2021-03-18 03:34:34 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 305 ms / 2,000 ms |
コード長 | 2,781 bytes |
コンパイル時間 | 193 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 110,080 KB |
最終ジャッジ日時 | 2024-11-15 21:26:02 |
合計ジャッジ時間 | 6,572 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
class UnionFind:def __init__(self, n):self.n = nself.parents = [-1] * ndef find(self, x):""" 根を見つける関数を定義(同時にxを直接根にくっつける操作も行う)"""tmp = []parents = self.parentswhile parents[x] >= 0:tmp.append(x)x = parents[x]for y in tmp:parents[y] = xreturn xdef union(self, x, y):""" 二つの木をくっつける(子を多く持つ方を根とした親子関係)。これは破壊的操作を行う。"""x = self.find(x)y = self.find(y)if x == y:returnif self.parents[x] > self.parents[y]:x, y = y, xself.parents[x] += self.parents[y]self.parents[y] = xdef same(self, x, y):""" xとyが同じ根の子かを判定 """return self.find(x) == self.find(y)def size(self, x):""" xの根のparent(= 要素数)を返す """return -self.parents[self.find(x)]def members(self, x):""" xが属するグループの要素をリストとして返す O(N)"""root = self.find(x)return [i for i in range(self.n) if self.find(i) == root]def roots(self):""" 全ての根の要素をリストとして返す O(N)"""return [i for i, x in enumerate(self.parents) if x < 0]def group_count(self):""" グループの数を返す O(N)"""return len(self.roots())def size_list(self):""" 各グループの要素数のリストを返す(根の番号は返さない) O(N)"""return [-x for x in self.parents if x < 0]def all_group_members(self):""" {根:[根の子(根を含む)のリスト],...}を辞書で返す O(N)"""res = [[] for _ in range(self.n)]for i in range(self.n):x = self.find(i)res[x].append(i)return {r: res[r] for r in self.roots()}def __str__(self):return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())##############################################################################################################import sysinput = sys.stdin.readlineN,D,W=map(int, input().split())U = UnionFind(N)V = UnionFind(N)for _ in range(D):a,b=map(int, input().split())U.union(a-1,b-1)for _ in range(W):a,b=map(int, input().split())V.union(a-1,b-1)res=0for root, mem in U.all_group_members().items():used=set()cnt2=0cnt1=len(mem)for i in mem:root2=V.find(i)if root2 not in used:size=V.size(i)cnt2+=sizeused.add(root2)res+=cnt1*(cnt1-1)res+=cnt1*(cnt2-cnt1)print(res)