結果
問題 | No.1293 2種類の道路 |
ユーザー |
![]() |
提出日時 | 2020-11-21 20:56:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 477 ms / 2,000 ms |
コード長 | 1,963 bytes |
コンパイル時間 | 224 ms |
コンパイル使用メモリ | 82,488 KB |
実行使用メモリ | 133,728 KB |
最終ジャッジ日時 | 2024-07-23 16:05:25 |
合計ジャッジ時間 | 6,425 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
class UnionFindNode:def __init__(self, group_id, parent=None, value=None):self.group_id_ = group_idself.parent_ = parentself.value = valueself.rank_ = 1self.member_num_ = 1def is_root(self):return not self.parent_def root(self):parent = selfwhile not parent.is_root():parent = parent.parent_self.parent_ = parentreturn parentdef find(self):root = self.root()return root.group_id_def rank(self):root = self.root()return root.rank_def unite(self, unite_node):root = self.root()unite_root = unite_node.root()if root.group_id_ != unite_root.group_id_:if root.rank() > unite_root.rank():n_root, child = root, unite_rootelse:n_root, child = unite_root, rootchild.parent_ = n_rootn_root.rank_ = max(n_root.rank_, child.rank_ + 1)n_root.member_num_ = n_root.member_num_ + child.member_num_if __name__ == "__main__":import sys;input=sys.stdin.readlineN, D, W = map(int, input().split())nodes1 = [UnionFindNode(i) for i in range(N+1)]for _ in range(D):a, b = map(int, input().split())nodes1[a].unite(nodes1[b])nodes2 = [UnionFindNode(i) for i in range(N+1)]for _ in range(W):a, b = map(int, input().split())nodes2[a].unite(nodes2[b])R = 0vs = set()from collections import defaultdictX = defaultdict(int)D = defaultdict(set)for i in range(1, N+1):x, y = nodes1[i].root().group_id_, nodes2[i].root().group_id_# if x in vs:# continue# vs.add(x)if y in D[x]:continueD[x].add(y)X[x] += nodes2[y].member_num_# print(D)for x in D:R += nodes1[x].member_num_ * (X[x]-1)print(R)