結果
問題 |
No.1293 2種類の道路
|
ユーザー |
![]() |
提出日時 | 2025-03-31 17:20:27 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 463 ms / 2,000 ms |
コード長 | 1,866 bytes |
コンパイル時間 | 402 ms |
コンパイル使用メモリ | 82,620 KB |
実行使用メモリ | 134,928 KB |
最終ジャッジ日時 | 2025-03-31 17:20:43 |
合計ジャッジ時間 | 7,278 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
import sys from collections import defaultdict class UnionFind: def __init__(self, size): self.parent = list(range(size + 1)) # 1-based indexing self.size = [1] * (size + 1) def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): x_root = self.find(x) y_root = self.find(y) if x_root == y_root: return if self.size[x_root] < self.size[y_root]: x_root, y_root = y_root, x_root self.parent[y_root] = x_root self.size[x_root] += self.size[y_root] def main(): input = sys.stdin.read().split() idx = 0 N = int(input[idx]); idx += 1 D = int(input[idx]); idx += 1 W = int(input[idx]); idx += 1 car_uf = UnionFind(N) for _ in range(D): a = int(input[idx]); idx += 1 b = int(input[idx]); idx += 1 car_uf.union(a, b) walk_uf = UnionFind(N) for _ in range(W): c = int(input[idx]); idx += 1 d = int(input[idx]); idx += 1 walk_uf.union(c, d) walk_size = {} for x in range(1, N + 1): root = walk_uf.find(x) if root not in walk_size: walk_size[root] = walk_uf.size[root] walk_to_cars = defaultdict(set) for x in range(1, N + 1): walk_r = walk_uf.find(x) car_c = car_uf.find(x) walk_to_cars[walk_r].add(car_c) M = defaultdict(int) for walk_r, cars in walk_to_cars.items(): s = walk_size[walk_r] for c in cars: M[c] += s car_reps = set() for x in range(1, N + 1): car_reps.add(car_uf.find(x)) ans = 0 for c in car_reps: m = M.get(c, 0) ans += car_uf.size[c] * max(m - 1, 0) print(ans) if __name__ == '__main__': main()