結果

問題 No.1293 2種類の道路
コンテスト
ユーザー ntuda
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
0