結果
問題 | No.1293 2種類の道路 |
ユーザー |
👑 ![]() |
提出日時 | 2020-11-20 22:18:42 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 307 ms / 2,000 ms |
コード長 | 2,021 bytes |
コンパイル時間 | 189 ms |
コンパイル使用メモリ | 82,012 KB |
実行使用メモリ | 112,804 KB |
最終ジャッジ日時 | 2024-07-23 13:15:00 |
合計ジャッジ時間 | 5,319 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
"""道路の種類ごとにunion-findする後は自動車専用道路と歩行者専用道路のリンクを考える…結局普通に数えたのではN**2になってしまうまとめて数える方法が必須歩行者側だけ繋いでおく…?後は連結成分だけ考えればいいはず自動車専用をつなぐと、そこの間の組が通行可能になる→まず歩行者側をつないで連結成分の親だけのグラフにするん~~~超頂点を作るX1,X2フロー!?DはX1側を交互につなぐ二部グラフにはなるけど…下側の連結成分をまとめておく上側もまとめておく上側を連結成分ごとに計算する下にある連結成分は高々N個なのでdictで重複を管理しつつやればO(NlogN)で解ける"""from sys import stdindef uf_find(n,p):ufl = []while p[n] != n:ufl.append(n)n = p[n]for i in ufl:p[i] = nreturn ndef uf_union(a,b,p,rank):ap = uf_find(a,p)bp = uf_find(b,p)if ap == bp:return Falseelse:if rank[ap] > rank[bp]:p[bp] = aprank[ap] += rank[bp]else:p[ap] = bprank[bp] += rank[ap]return TrueN,D,W = map(int,stdin.readline().split())ab = []for i in range(D):a,b = map(int,stdin.readline().split())ab.append((a-1,b-1))cd = []for i in range(W):c,d = map(int,stdin.readline().split())cd.append((c-1,d-1))p1 = [i for i in range(N)]rank1 = [1] * Nfor a,b in ab:uf_union(a,b,p1,rank1)p2 = [i for i in range(N)]rank2 = [1] * Nfor c,d in cd:uf_union(c,d,p2,rank2)ans = 0ch = [ {} for i in range(N) ]for i in range(N):underP = uf_find(i,p2)ch[uf_find(i,p1)][underP] = rank2[underP]#print (ch)ans = 0for i in range(N):if len(ch[i]) > 0:tsum = 0for key in ch[i]:tsum += ch[i][key]ans += rank1[i] * tsumprint (ans - N)