結果
問題 | No.1293 2種類の道路 |
ユーザー |
![]() |
提出日時 | 2020-11-20 21:37:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 301 ms / 2,000 ms |
コード長 | 1,976 bytes |
コンパイル時間 | 140 ms |
コンパイル使用メモリ | 82,496 KB |
実行使用メモリ | 101,560 KB |
最終ジャッジ日時 | 2024-07-23 12:45:53 |
合計ジャッジ時間 | 4,691 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
mod = 1000000007eps = 10**-9def main():import sysfrom collections import dequeinput = sys.stdin.buffer.readlineclass UnionFind():def __init__(self, n):self.n = nself.root = [-1] * (n + 1)self.rnk = [0] * (n + 1)def find_root(self, x):while self.root[x] >= 0:x = self.root[x]return xdef unite(self, x, y):x = self.find_root(x)y = self.find_root(y)if x == y:returnelif self.rnk[x] > self.rnk[y]:self.root[x] += self.root[y]self.root[y] = xelse:self.root[y] += self.root[x]self.root[x] = yif self.rnk[x] == self.rnk[y]:self.rnk[y] += 1def isSameGroup(self, x, y):return self.find_root(x) == self.find_root(y)def size(self, x):return -self.root[self.find_root(x)]N, D, W = map(int, input().split())adj = [[] for _ in range(N+1)]for _ in range(D):a, b = map(int, input().split())adj[a].append(b)adj[b].append(a)UF = UnionFind(N)for _ in range(W):a, b = map(int, input().split())UF.unite(a, b)seen = [0] * (N+1)ans = -Nfor v0 in range(1, N+1):if seen[v0]:continueseen[v0] = 1seen_w = set()que = deque()que.append(v0)cnt_d = 0cnt_w = 0while que:v = que.popleft()cnt_d += 1r = UF.find_root(v)if r not in seen_w:seen_w.add(r)cnt_w += -UF.root[r]for u in adj[v]:if not seen[u]:seen[u] = 1que.append(u)ans += cnt_w * cnt_dprint(ans)if __name__ == '__main__':main()