結果

問題 No.1254 補強への架け橋
ユーザー marroncastlemarroncastle
提出日時 2020-10-10 02:03:51
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,872 bytes
コンパイル時間 747 ms
コンパイル使用メモリ 86,740 KB
実行使用メモリ 296,320 KB
最終ジャッジ日時 2023-09-27 20:56:00
合計ジャッジ時間 32,851 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 98 ms
80,396 KB
testcase_01 AC 100 ms
76,044 KB
testcase_02 AC 99 ms
76,196 KB
testcase_03 AC 97 ms
76,052 KB
testcase_04 AC 97 ms
76,028 KB
testcase_05 AC 96 ms
76,244 KB
testcase_06 AC 99 ms
75,728 KB
testcase_07 AC 100 ms
76,124 KB
testcase_08 AC 101 ms
76,020 KB
testcase_09 AC 102 ms
76,020 KB
testcase_10 AC 101 ms
76,020 KB
testcase_11 AC 99 ms
76,044 KB
testcase_12 AC 100 ms
76,040 KB
testcase_13 AC 102 ms
75,980 KB
testcase_14 AC 99 ms
76,140 KB
testcase_15 AC 99 ms
76,140 KB
testcase_16 AC 99 ms
75,760 KB
testcase_17 AC 101 ms
76,052 KB
testcase_18 AC 95 ms
76,204 KB
testcase_19 AC 102 ms
75,952 KB
testcase_20 AC 102 ms
75,960 KB
testcase_21 AC 98 ms
76,032 KB
testcase_22 AC 99 ms
76,132 KB
testcase_23 AC 99 ms
75,960 KB
testcase_24 AC 99 ms
76,104 KB
testcase_25 AC 98 ms
76,080 KB
testcase_26 AC 102 ms
75,764 KB
testcase_27 AC 100 ms
76,196 KB
testcase_28 AC 101 ms
76,072 KB
testcase_29 AC 102 ms
75,976 KB
testcase_30 AC 102 ms
76,136 KB
testcase_31 AC 97 ms
76,104 KB
testcase_32 AC 99 ms
75,912 KB
testcase_33 AC 102 ms
76,140 KB
testcase_34 AC 96 ms
76,100 KB
testcase_35 AC 98 ms
75,908 KB
testcase_36 AC 103 ms
76,128 KB
testcase_37 AC 105 ms
76,148 KB
testcase_38 AC 102 ms
76,140 KB
testcase_39 AC 101 ms
76,164 KB
testcase_40 AC 103 ms
76,136 KB
testcase_41 AC 99 ms
76,076 KB
testcase_42 AC 101 ms
75,960 KB
testcase_43 AC 121 ms
77,704 KB
testcase_44 AC 102 ms
76,032 KB
testcase_45 AC 99 ms
76,164 KB
testcase_46 AC 110 ms
77,644 KB
testcase_47 AC 103 ms
75,988 KB
testcase_48 AC 104 ms
76,240 KB
testcase_49 AC 100 ms
75,784 KB
testcase_50 AC 110 ms
77,412 KB
testcase_51 AC 109 ms
77,856 KB
testcase_52 AC 110 ms
77,580 KB
testcase_53 AC 112 ms
77,784 KB
testcase_54 AC 106 ms
77,584 KB
testcase_55 AC 108 ms
77,708 KB
testcase_56 AC 100 ms
75,724 KB
testcase_57 AC 121 ms
77,000 KB
testcase_58 AC 112 ms
77,572 KB
testcase_59 AC 98 ms
76,036 KB
testcase_60 AC 99 ms
75,988 KB
testcase_61 AC 107 ms
76,996 KB
testcase_62 AC 104 ms
75,988 KB
testcase_63 AC 168 ms
85,636 KB
testcase_64 AC 136 ms
80,108 KB
testcase_65 AC 161 ms
83,012 KB
testcase_66 AC 150 ms
81,740 KB
testcase_67 AC 129 ms
79,632 KB
testcase_68 AC 153 ms
82,504 KB
testcase_69 AC 163 ms
83,668 KB
testcase_70 AC 139 ms
80,444 KB
testcase_71 AC 130 ms
79,512 KB
testcase_72 AC 166 ms
83,680 KB
testcase_73 AC 136 ms
79,540 KB
testcase_74 AC 156 ms
82,640 KB
testcase_75 AC 156 ms
81,856 KB
testcase_76 AC 120 ms
78,004 KB
testcase_77 AC 149 ms
81,612 KB
testcase_78 AC 163 ms
85,204 KB
testcase_79 AC 164 ms
84,716 KB
testcase_80 AC 169 ms
84,504 KB
testcase_81 AC 170 ms
85,124 KB
testcase_82 AC 170 ms
84,068 KB
testcase_83 AC 371 ms
122,516 KB
testcase_84 AC 355 ms
116,916 KB
testcase_85 AC 258 ms
107,824 KB
testcase_86 AC 318 ms
113,084 KB
testcase_87 AC 349 ms
115,260 KB
testcase_88 AC 188 ms
88,764 KB
testcase_89 AC 357 ms
122,452 KB
testcase_90 AC 280 ms
110,288 KB
testcase_91 AC 248 ms
102,824 KB
testcase_92 AC 203 ms
91,064 KB
testcase_93 AC 302 ms
111,784 KB
testcase_94 AC 281 ms
112,764 KB
testcase_95 AC 293 ms
111,300 KB
testcase_96 AC 323 ms
117,832 KB
testcase_97 AC 233 ms
99,988 KB
testcase_98 AC 352 ms
116,960 KB
testcase_99 AC 262 ms
106,692 KB
testcase_100 AC 362 ms
123,008 KB
testcase_101 AC 193 ms
91,768 KB
testcase_102 AC 176 ms
86,788 KB
testcase_103 AC 194 ms
90,836 KB
testcase_104 AC 215 ms
95,536 KB
testcase_105 AC 304 ms
111,844 KB
testcase_106 AC 232 ms
101,120 KB
testcase_107 AC 360 ms
122,460 KB
testcase_108 AC 345 ms
117,424 KB
testcase_109 AC 296 ms
111,820 KB
testcase_110 AC 287 ms
111,244 KB
testcase_111 AC 294 ms
111,712 KB
testcase_112 AC 213 ms
95,480 KB
testcase_113 AC 292 ms
111,228 KB
testcase_114 AC 236 ms
101,300 KB
testcase_115 AC 182 ms
87,992 KB
testcase_116 AC 235 ms
104,188 KB
testcase_117 AC 191 ms
92,988 KB
testcase_118 AC 317 ms
117,448 KB
testcase_119 AC 236 ms
106,704 KB
testcase_120 AC 308 ms
114,820 KB
testcase_121 AC 198 ms
92,512 KB
testcase_122 AC 246 ms
103,952 KB
testcase_123 AC 96 ms
76,104 KB
testcase_124 TLE -
testcase_125 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys,os,io
input = sys.stdin.readline
from collections import defaultdict
class Graph:
  def __init__(self, N):
    self.V = N
    self.edge = [[] for _ in range(self.V)]
    self.edges = defaultdict(lambda: 0)
    self.visited = [0]*N
    self.parent = [N]*N
  
  def add_edge(self, a, b, i):
    self.edge[a].append(b)
    self.edges[(a,b)] = i

  def dfs(self, start):
    stack = [start]
    self.parent[start] = -1
    self.visited[start] = 1
    #記録したい値の配列を定義
    while stack:
      v = stack[-1]
      for u,i in self.edge[v]:
        if u==self.parent[v]:
          continue
        if self.parent[u]==N: #子へ降ろす
          self.parent[u]=v
          stack.append(u)
          break
        else:
          return u
      else:
        stack.pop()

  def bfs1(self, start):
    stack = deque([start])
    self.parent[start] = -1
    while stack:
      v = stack.pop()
      for u in self.edge[v]:
        if u==self.parent[v]:
          continue
        if self.parent[u]!=N:
          return u
        self.parent[u]=v
        #頂点に対する処理
        stack.append(u)
    return
  
  
  def bfs(self, start):
    d = deque()
    d.append([start])
    cyc = []
    self.visited[start] = True
    while len(d)>0:
      vs = d.popleft()
      for w in self.edge[vs[-1]]:
        if len(vs)>1 and w==vs[-2]:
          continue
        cyc = copy(vs)
        cyc.append(w)
        if w==start:
          return cyc
        d.append(cyc)
    return cyc

from collections import deque
from copy import copy

N = int(input())
G = Graph(N)
for i in range(N):
  a,b = map(int, input().split())
  a,b = min(a-1,b-1), max(a-1,b-1)
  G.add_edge(a,b,i+1)
  G.add_edge(b,a,i+1)

ans = set()
cyc = G.bfs1(0)
vs = G.bfs(cyc)
for v0,v1 in zip(vs[:-1],vs[1:]):
  ans.add(G.edges[(v0,v1)])
ans = list(ans)
print(len(ans))
print(*ans)
0