結果
問題 | No.1254 補強への架け橋 |
ユーザー |
👑 ![]() |
提出日時 | 2020-08-09 23:38:47 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 869 bytes |
コンパイル時間 | 243 ms |
コンパイル使用メモリ | 82,128 KB |
実行使用メモリ | 129,392 KB |
最終ジャッジ日時 | 2024-10-13 18:18:04 |
合計ジャッジ時間 | 27,614 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 3 |
other | WA * 123 |
ソースコード
from collections import dequeN=int(input())E={v:set() for v in range(1,N+1)}F={}for _ in range(N):a,b=map(int,input().split())E[a].add(b)E[b].add(a)a,b=min(a,b),max(a,b)F[(a,b)]=FalseT=[False]*(N+1)S=deque([1])T[1]=Truewhile S:v=S.pop()for u in E[v]:if not T[u]:S.append(u)T[u]=Truea,b=min(u,v),max(u,v)F[(a,b)]=Truep,q=min(F,key=lambda x:F[x])E[p].remove(q)E[q].remove(p)T=[0]*(N+1)D=[0]*(N+1)S=deque([p])T[p]=float("inf")while S:v=S.pop()for u in E[v]:if not T[u]:S.append(u)D[u]=D[v]+1T[u]=vH=D[q]P=[0]*(H+1)P[0]=qy=qi=0while y!=p:i+=1y=T[y]P[i]=yprint(H+1)X=[(p,q)]+[(P[i],P[i+1]) for i in range(H)]print("\n".join(map(lambda x:"{} {}".format(x[0],x[1]),X)))