結果
問題 | No.1293 2種類の道路 |
ユーザー |
![]() |
提出日時 | 2020-11-26 17:44:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 424 ms / 2,000 ms |
コード長 | 1,228 bytes |
コンパイル時間 | 618 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 111,844 KB |
最終ジャッジ日時 | 2024-07-23 20:54:55 |
合計ジャッジ時間 | 6,461 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
import sysfrom collections import dequedef MI(): return map(int,sys.stdin.readline().rstrip().split())N,D,W = MI()Graph0 = [[] for _ in range(N+1)]for _ in range(D):a,b = MI()Graph0[a].append(b)Graph0[b].append(a)Graph1 = [[] for _ in range(N+1)]for _ in range(W):c,d = MI()Graph1[c].append(d)Graph1[d].append(c)count = [] # 各連結成分の要素数X = [-1]*(N+1) # 各頂点が何番目の連結成分に属しているかa = 0for i in range(1,N+1):if X[i] != -1:continuedeq = deque([i])X[i] = ac = 1while deq:j = deq.pop()for k in Graph0[j]:if X[k] == -1:X[k] = adeq.append(k)c += 1count.append(c)a += 1ans = 0flag = [0]*(N+1)for i in range(1,N+1):if flag[i] == 1:continueA = []deq = deque([i])flag[i] = 1A.append(X[i])c = 1while deq:j = deq.pop()for k in Graph1[j]:if flag[k] == 0:flag[k] = 1deq.append(k)A.append(X[k])c += 1A = list(set(A))for a in A:ans += c*count[a]print(ans-N)