結果
問題 |
No.1293 2種類の道路
|
ユーザー |
![]() |
提出日時 | 2025-07-15 21:27:49 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,132 bytes |
コンパイル時間 | 523 ms |
コンパイル使用メモリ | 82,792 KB |
実行使用メモリ | 67,824 KB |
最終ジャッジ日時 | 2025-07-15 21:27:54 |
合計ジャッジ時間 | 4,127 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | RE * 2 |
other | RE * 22 |
ソースコード
from atcoder.dsu import DSU N,D,W = map(int,input().split()) dsu1 = DSU(N) dsu2 = DSU(N) for _ in range(D): a,b = map(int,input().split()) a -= 1 b -= 1 dsu1.merge(a,b) for _ in range(W): c,d = map(int,input().split()) c -= 1 d -= 1 dsu2.merge(c,d) ans = 0 G1 = dsu1.groups() G2 = dsu2.groups() G3 = [] G3all = set() G4 = [] for G in G1: n = len(G) if n > 1: ans += n * (n-1) G3.append(set(G)) for G in G2: n = len(G) if n > 1: ans += n * (n-1) G4.append(set(G)) X1 = [-1] * N X2 = [-1] * N N1 = len(G3) N2 = len(G4) for i,gs in enumerate(G3): for g in gs: X1[g] = i for i,gs in enumerate(G4): for g in gs: X2[g] = i Y1 = [0] * N1 Y2 = [0] * N2 Y12 = [0] * N2 Y2C = [0] * N2 for i in range(N): if X1[i] == -1: if X2[i] == -1: continue else: Y2[X2[i]] += 1 else: Y1[X1[i]] += 1 if X2[i] > -1: Y12[X2[i]] += 1 Y2C[X1[i]] = X2[i] for i in range(N2): ans -= Y12[i] * (Y12[i] - 1) ans += (Y1[Y2C[i]] - Y12[i]) * Y2[i] print(ans)