結果
問題 | No.1293 2種類の道路 |
ユーザー |
![]() |
提出日時 | 2020-11-22 20:43:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 355 ms / 2,000 ms |
コード長 | 1,475 bytes |
コンパイル時間 | 2,290 ms |
コンパイル使用メモリ | 81,736 KB |
実行使用メモリ | 124,264 KB |
最終ジャッジ日時 | 2024-07-23 16:45:15 |
合計ジャッジ時間 | 6,420 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
import sysinput = sys.stdin.readlinefrom collections import *class Unionfind:def __init__(self, n):self.par = [-1]*nself.rank = [1]*ndef root(self, x):r = xwhile not self.par[r]<0:r = self.par[r]t = xwhile t!=r:tmp = tt = self.par[t]self.par[tmp] = rreturn rdef unite(self, x, y):rx = self.root(x)ry = self.root(y)if rx==ry:returnif self.rank[rx]<=self.rank[ry]:self.par[ry] += self.par[rx]self.par[rx] = ryif self.rank[rx]==self.rank[ry]:self.rank[ry] += 1else:self.par[rx] += self.par[ry]self.par[ry] = rxdef is_same(self, x, y):return self.root(x)==self.root(y)def count(self, x):return -self.par[self.root(x)]N, D, W = map(int, input().split())uf1 = Unionfind(N)uf2 = Unionfind(N)for _ in range(D):a, b = map(int, input().split())uf1.unite(a-1, b-1)for _ in range(W):c, d = map(int, input().split())uf2.unite(c-1, d-1)d = defaultdict(set)for i in range(N):d[uf1.root(i)].add(uf2.root(i))cnt = defaultdict(int)for k in d:for v in d[k]:cnt[k] += uf2.count(v)ans = 0for i in range(N):ans += cnt[uf1.root(i)]-1print(ans)