結果
問題 | No.1293 2種類の道路 |
ユーザー |
![]() |
提出日時 | 2022-06-10 00:46:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 260 ms / 2,000 ms |
コード長 | 1,364 bytes |
コンパイル時間 | 152 ms |
コンパイル使用メモリ | 82,496 KB |
実行使用メモリ | 103,308 KB |
最終ジャッジ日時 | 2024-09-21 05:40:08 |
合計ジャッジ時間 | 5,641 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
from collections import defaultdictimport sysinput = sys.stdin.buffer.readlinesys.setrecursionlimit(10 ** 7)class UF_tree:def __init__(self, n):self.root = [-1] * (n + 1)def find(self, x):stack = []while self.root[x] >= 0:stack.append(x)x = self.root[x]for i in stack:self.root[i] = xreturn xdef same(self, x, y):return self.find(x) == self.find(y)def unite(self, x, y):x = self.find(x)y = self.find(y)if x == y:return Falseif -self.root[x] > -self.root[y]:x, y = y, xself.root[y] += self.root[x]self.root[x] = yreturn Truedef size(self, x):return -self.root[self.find(x)]N, D, W = map(int, input().split())car = UF_tree(N)walk = UF_tree(N)for _ in range(D):a, b = map(int, input().split())car.unite(a-1, b-1)for _ in range(W):a, b = map(int, input().split())walk.unite(a-1, b-1)ans = 0group = defaultdict(list)for i in range(N):group[car.find(i)].append(i)ans = 0for k in group.keys():used = set()sz = 0for i in group[k]:x = walk.find(i)if x in used:continuesz += walk.size(x)used.add(x)ans += len(group[k]) * szprint(ans - N)