結果
問題 | No.1293 2種類の道路 |
ユーザー |
![]() |
提出日時 | 2020-11-21 01:28:18 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 896 ms / 2,000 ms |
コード長 | 1,693 bytes |
コンパイル時間 | 203 ms |
コンパイル使用メモリ | 13,056 KB |
実行使用メモリ | 52,404 KB |
最終ジャッジ日時 | 2024-07-23 14:14:51 |
合計ジャッジ時間 | 11,094 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
import sysinput = sys.stdin.readlineN,D,W=map(int,input().split())# UnionFindGroup0 = [i for i in range(N+1)] # グループ分けNodes0 = [1]*(N+1) # 各グループのノードの数def find(x):while Group0[x] != x:x=Group0[x]return xdef Union(x,y):if find(x) != find(y):if Nodes0[find(x)] < Nodes0[find(y)]:Nodes0[find(y)] += Nodes0[find(x)]Nodes0[find(x)] = 0Group0[find(x)] = find(y)else:Nodes0[find(x)] += Nodes0[find(y)]Nodes0[find(y)] = 0Group0[find(y)] = find(x)# UnionFindGroup1 = [i for i in range(N+1)] # グループ分けNodes1 = [1]*(N+1) # 各グループのノードの数def find1(x):while Group1[x] != x:x=Group1[x]return xdef Union1(x,y):if find1(x) != find1(y):if Nodes1[find1(x)] < Nodes1[find1(y)]:Nodes1[find1(y)] += Nodes1[find1(x)]Nodes1[find1(x)] = 0Group1[find1(x)] = find1(y)else:Nodes1[find1(x)] += Nodes1[find1(y)]Nodes1[find1(y)] = 0Group1[find1(y)] = find1(x)for i in range (D):x,y=map(int,input().split())Union(x,y)for i in range(W):x,y=map(int,input().split())Union1(x,y)G1_to_G0=[set() for i in range(N+1)]for i in range(N+1):G1_to_G0[find1(i)].add(find(i))NGroup=[0]*(N+1)for i in range(N+1):if find1(i)==i:for g0 in G1_to_G0[i]:NGroup[g0]+=Nodes1[i]ANS=0for i in range(1,N+1):if Nodes0[i]==0:continueANS+=Nodes0[i]*(NGroup[i]-1)print(ANS)