結果
問題 |
No.1293 2種類の道路
|
ユーザー |
![]() |
提出日時 | 2025-03-26 15:44:26 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 437 ms / 2,000 ms |
コード長 | 1,591 bytes |
コンパイル時間 | 415 ms |
コンパイル使用メモリ | 82,708 KB |
実行使用メモリ | 128,236 KB |
最終ジャッジ日時 | 2025-03-26 15:44:50 |
合計ジャッジ時間 | 5,943 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
class DSU: 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 # Union by size 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(): import sys input = sys.stdin.read().split() ptr = 0 N = int(input[ptr]) ptr += 1 D = int(input[ptr]) ptr += 1 W = int(input[ptr]) ptr += 1 # Initialize DSU for car and pedestrian roads car_dsu = DSU(N) for _ in range(D): a = int(input[ptr]) ptr += 1 b = int(input[ptr]) ptr += 1 car_dsu.union(a, b) ped_dsu = DSU(N) for _ in range(W): c = int(input[ptr]) ptr += 1 d = int(input[ptr]) ptr += 1 ped_dsu.union(c, d) # Collect unique (car_root, ped_root) pairs unique_pairs = set() for node in range(1, N + 1): cr = car_dsu.find(node) pr = ped_dsu.find(node) unique_pairs.add((cr, pr)) total = 0 for (cr, pr) in unique_pairs: total += car_dsu.size[cr] * ped_dsu.size[pr] ans = total - N print(ans) if __name__ == '__main__': main()