結果
| 問題 | No.1254 補強への架け橋 |
| ユーザー |
👑  Kazun
|
| 提出日時 | 2020-08-09 03:58:45 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 4,681 bytes |
| コンパイル時間 | 401 ms |
| コンパイル使用メモリ | 82,432 KB |
| 実行使用メモリ | 906,544 KB |
| 最終ジャッジ日時 | 2024-04-21 19:29:08 |
| 合計ジャッジ時間 | 33,575 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | MLE | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
| testcase_36 | WA | - |
| testcase_37 | WA | - |
| testcase_38 | WA | - |
| testcase_39 | WA | - |
| testcase_40 | WA | - |
| testcase_41 | WA | - |
| testcase_42 | WA | - |
| testcase_43 | WA | - |
| testcase_44 | WA | - |
| testcase_45 | WA | - |
| testcase_46 | WA | - |
| testcase_47 | WA | - |
| testcase_48 | WA | - |
| testcase_49 | WA | - |
| testcase_50 | WA | - |
| testcase_51 | WA | - |
| testcase_52 | WA | - |
| testcase_53 | WA | - |
| testcase_54 | WA | - |
| testcase_55 | WA | - |
| testcase_56 | WA | - |
| testcase_57 | WA | - |
| testcase_58 | WA | - |
| testcase_59 | WA | - |
| testcase_60 | WA | - |
| testcase_61 | WA | - |
| testcase_62 | WA | - |
| testcase_63 | WA | - |
| testcase_64 | WA | - |
| testcase_65 | WA | - |
| testcase_66 | WA | - |
| testcase_67 | WA | - |
| testcase_68 | WA | - |
| testcase_69 | WA | - |
| testcase_70 | WA | - |
| testcase_71 | WA | - |
| testcase_72 | WA | - |
| testcase_73 | WA | - |
| testcase_74 | WA | - |
| testcase_75 | WA | - |
| testcase_76 | WA | - |
| testcase_77 | WA | - |
| testcase_78 | WA | - |
| testcase_79 | WA | - |
| testcase_80 | WA | - |
| testcase_81 | WA | - |
| testcase_82 | WA | - |
| testcase_83 | WA | - |
| testcase_84 | WA | - |
| testcase_85 | WA | - |
| testcase_86 | WA | - |
| testcase_87 | WA | - |
| testcase_88 | WA | - |
| testcase_89 | WA | - |
| testcase_90 | WA | - |
| testcase_91 | WA | - |
| testcase_92 | WA | - |
| testcase_93 | WA | - |
| testcase_94 | WA | - |
| testcase_95 | WA | - |
| testcase_96 | WA | - |
| testcase_97 | WA | - |
| testcase_98 | WA | - |
| testcase_99 | WA | - |
| testcase_100 | WA | - |
| testcase_101 | WA | - |
| testcase_102 | WA | - |
| testcase_103 | WA | - |
| testcase_104 | WA | - |
| testcase_105 | WA | - |
| testcase_106 | WA | - |
| testcase_107 | WA | - |
| testcase_108 | WA | - |
| testcase_109 | WA | - |
| testcase_110 | WA | - |
| testcase_111 | WA | - |
| testcase_112 | WA | - |
| testcase_113 | WA | - |
| testcase_114 | WA | - |
| testcase_115 | WA | - |
| testcase_116 | WA | - |
| testcase_117 | WA | - |
| testcase_118 | WA | - |
| testcase_119 | WA | - |
| testcase_120 | WA | - |
| testcase_121 | WA | - |
| testcase_122 | WA | - |
| testcase_123 | WA | - |
| testcase_124 | MLE | - |
| testcase_125 | -- | - |
ソースコード
class Graph:
#入力定義
def __init__(self,vertex=[]):
self.vertex=list(vertex)
self.edge_number=0
self.adjacent={v:set() for v in vertex}
#頂点の追加
def add_vertex(self,*adder):
k=len(self.vertex)
m=0
for u in adder:
if u not in self.adjacent:
self.adjacent[u]=set()
self.vertex.append(u)
#辺の追加
def add_edge(self,From,To):
for w in [From,To]:
if w not in self.adjacent:
self.add_vertex(w)
if To not in self.adjacent[From]:
self.adjacent[From].add(To)
self.adjacent[To].add(From)
self.edge_number+=1
#辺を除く
def remove_edge(self,u,v):
for w in [u,v]:
if w not in self.adjacent:
self.add_vertex(w)
if u in self.adjacent[v]:
self.adjacent[u].remove(v)
self.adjacent[v].remove(u)
self.edge_number-=1
#頂点を除く
def remove_vertex(self,*v):
for w in v:
if w in self.adjacent:
self.edge_number-=len(self.adjacent[w])
for u in self.adjacent[w]:
self.adjacent[u].remove(w)
del self.adjacent[w]
#Walkの追加
def add_walk(self,*walk):
n=len(walk)
for i in range(n-1):
self.add_edge(walk[i],walk[i+1])
#Cycleの追加
def add_cycle(self,*cycle):
self.add_walk(*cycle)
self.add_edge(cycle[-1],cycle[0])
#頂点の交換
def __vertex_swap(self,p,q):
self.vertex.sort()
#グラフに頂点が存在するか否か
def vertex_exist(self,v):
return v in self.adjacent
#グラフに辺が存在するか否か
def edge_exist(self,u,v):
if not(self.vertex_exist(u) and self.vertex_exist(v)):
return False
return u in self.adjacent[v]
#近傍
def neighbohood(self,v):
if not self.vertex_exist(v):
return []
return list(self.adjacent[v])
#次数
def degree(self,v):
if not self.vertex_exist(v):
return 0
return len(self.adjacent[v])
#頂点数
def vertex_count(self):
return len(self.vertex)
#辺数
def edge_count(self):
return self.edge_number
#頂点vを含む連結成分
def connected_component(self,v):
if v not in self.adjacent:
return []
from collections import deque
T={u:False for u in self.adjacent}
T[v]=True
S=deque([v])
while S:
u=S.popleft()
for w in self.adjacent[u]:
if not T[w]:
T[w]=True
S.append(w)
return [x for x in self.adjacent if T[x]]
#距離
def distance(self,u,v):
from collections import deque
inf=float("inf")
T={v:inf for v in G.vertex}
if u==v:
return 0
Q=deque([u])
T[u]=0
while Q:
w=Q.popleft()
for x in G.adjacent[w]:
if T[x]==inf:
T[x]=T[w]+1
Q.append(x)
if x==v:
return T[x]
return inf
#最短路
def shortest_path(self,u,v):
from collections import deque
inf=float("inf")
T={v:[] for v in G.vertex}
if u==v:
return 0
Q=deque([u])
T[u]=[u]
while Q:
w=Q.popleft()
for x in G.adjacent[w]:
if not T[x]:
T[x]=T[w]+[x]
Q.append(x)
if x==v:
return T[x]
return None
def DFS_Tree(G):
from collections import deque
T={v:False for v in G.vertex}
v=G.vertex[0]
D={v:float("inf") for v in G.vertex}
S=deque([v])
T[v]=True
while S:
v=S.pop()
for u in G.adjacent[v]:
if not T[u]:
T[u]=True
S.append(u)
B.remove((min(u,v),max(u,v)))
#-------------------------------------------------
from collections import deque
N=int(input())
G=Graph(list(range(1,N+1)))
B=set()
for _ in range(N):
u,v=map(int,input().split())
G.add_edge(u,v)
x,y=min(u,v),max(u,v)
B.add((x,y))
DFS_Tree(G)
u,v=B.pop()
G.remove_edge(u,v)
P=G.shortest_path(u,v)+[u]
L=len(P)-1
X=[0]*L
for i in range(L):
a,b=min(P[i],P[i+1]),max(P[i],P[i+1])
X[i]=(a,b)
X.sort()
print(L)
print("\n".join(map(lambda x:"{} {}".format(x[0],x[1]),X)))