結果

問題 No.1293 2種類の道路
コンテスト
ユーザー ああ
提出日時 2026-05-17 23:05:26
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 299 ms / 2,000 ms
コード長 804 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 351 ms
コンパイル使用メモリ 85,504 KB
実行使用メモリ 113,664 KB
最終ジャッジ日時 2026-05-17 23:05:33
合計ジャッジ時間 6,574 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_1
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def aa(uf,m):
    c=[]
    while m!=uf[m]:
        c.append(m)
        m=uf[m]
    for i in c:
        uf[i]=m
    return m

n,d,w=map(int,input().split())
uf1=[i for i in range(n)]
x1=[1]*n
for i in range(d):
    a,b=map(int,input().split());a-=1;b-=1
    a,b=aa(uf1,a),aa(uf1,b)
    if a==b:
        continue
    uf1[b]=a
    x1[a]+=x1[b]
uf2=[i for i in range(n)]
x2=[1]*n
z=[0]*n;ans=0
for i in range(w):
    a,b=map(int,input().split());a-=1;b-=1
    a,b=aa(uf2,a),aa(uf2,b)
    if a==b:
        continue
    uf2[b]=a
    x2[a]+=x2[b]
y=[set() for i in range(n)]
for i in range(n):
    a,b=aa(uf1,i),aa(uf2,i)
    if b in y[a]:
        continue
    z[a]+=x2[b];y[a].add(b)
for i in range(n):
    if aa(uf2,i) not in y[aa(uf1,i)]:
    	z[aa(uf1,i)]+=1
for i in range(n):
	ans+=z[i]*x1[i]
print(ans-n)
0