結果
問題 | No.1293 2種類の道路 |
ユーザー | persimmon-persimmon |
提出日時 | 2021-02-16 13:39:54 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 507 ms / 2,000 ms |
コード長 | 2,281 bytes |
コンパイル時間 | 319 ms |
コンパイル使用メモリ | 87,184 KB |
実行使用メモリ | 142,480 KB |
最終ジャッジ日時 | 2023-10-11 02:03:30 |
合計ジャッジ時間 | 8,453 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 76 ms
71,328 KB |
testcase_01 | AC | 70 ms
71,476 KB |
testcase_02 | AC | 70 ms
71,124 KB |
testcase_03 | AC | 72 ms
71,276 KB |
testcase_04 | AC | 71 ms
71,328 KB |
testcase_05 | AC | 70 ms
71,496 KB |
testcase_06 | AC | 70 ms
71,436 KB |
testcase_07 | AC | 71 ms
71,452 KB |
testcase_08 | AC | 70 ms
71,584 KB |
testcase_09 | AC | 507 ms
125,116 KB |
testcase_10 | AC | 483 ms
125,388 KB |
testcase_11 | AC | 477 ms
125,056 KB |
testcase_12 | AC | 487 ms
125,592 KB |
testcase_13 | AC | 484 ms
124,964 KB |
testcase_14 | AC | 343 ms
142,216 KB |
testcase_15 | AC | 353 ms
142,480 KB |
testcase_16 | AC | 364 ms
134,920 KB |
testcase_17 | AC | 371 ms
141,924 KB |
testcase_18 | AC | 292 ms
137,376 KB |
testcase_19 | AC | 362 ms
135,288 KB |
testcase_20 | AC | 349 ms
135,960 KB |
testcase_21 | AC | 252 ms
99,120 KB |
testcase_22 | AC | 249 ms
99,080 KB |
testcase_23 | AC | 252 ms
98,876 KB |
ソースコード
# UnionFind class UnionFind: def __init__(self,n): self.n=n self.par=[-1]*n # par[i]:i根ならグループiの要素数に-1をかけたもの。i根じゃないならiの親 self.rank=[0]*n # iの根を返す def find(self,i): if self.par[i]<0:return i ii=i while self.par[i]>=0: i=self.par[i] while i!=self.par[ii]: ii,self.par[ii]=self.par[ii],i return i # iとjをunionし、根頂点を返す def union(self,i,j): i,j=self.find(i),self.find(j) if i==j:return i elif self.rank[i]>self.rank[j]: # par[i]:グループiの要素数で判断してもいい self.par[i]+=self.par[j] self.par[j]=i else: self.par[j]+=self.par[i] self.par[i]=j # 深さ(rank)が同じものを併合した場合1を足す if self.rank[i]==self.rank[j]: self.rank[j]+=1 return self.find(i) # iとjが同じグループに属するか判断 def same(self,i,j): return self.find(i)==self.find(j) # ノードiが属する木のサイズを返す def size(self,i): return -self.par[self.find(i)] def members(self): d={} for i in range(n): p=self.find(i) if p in d: d[p].add(i) else: d[p]={i} return d def main1(n,d,w,uv,st): ufd=UnionFind(n) for u,v in uv: u,v=u-1,v-1 ufd.union(u,v) ufw=UnionFind(n) for s,t in st: s,t=s-1,t-1 ufw.union(s,t) ans=0 mbd=ufd.members() mbw=ufw.members() for p in mbd: # 自動車用道路連結成分pを考える。 # pの各都市から歩行者用道路を0本以上使って行ける都市が到達可能な都市。 # size(p)=1の場合、自動車用道路を0本使うケースを数えることになる。 # 到達可能な都市数 abl=0 # 加算済み歩行者用道路連結成分を記録する。 su=set() for m in mbd[p]: pm=ufw.find(m) if pm not in su: su.add(pm) abl+=len(mbw[pm]) ans+=(abl-1)*(len(mbd[p])) return ans import sys input=sys.stdin.readline if __name__=='__main__': n,d,w=map(int,input().split()) uv=[list(map(int,input().split())) for _ in range(d)] st=[list(map(int,input().split())) for _ in range(w)] ret1=main1(n,d,w,uv,st) print(ret1)