#565512 (PyPy3) No.1254 補強への架け橋

提出ソース

結果

問題	No.1254 補強への架け橋
ユーザー	marroncastle
提出日時	2020-10-10 06:26:32
言語	PyPy3 (7.3.15)
結果	AC
実行時間	364 ms / 2,000 ms
コード長	1,487 bytes
コンパイル時間	1,660 ms
コンパイル使用メモリ	86,784 KB
実行使用メモリ	110,748 KB
最終ジャッジ日時	2023-09-27 21:06:32
合計ジャッジ時間	28,334 ms
ジャッジサーバーID （参考情報）	judge15 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	87 ms 71,388 KB
testcase_01	AC	91 ms 71,576 KB
testcase_02	AC	86 ms 71,528 KB
testcase_03	AC	88 ms 71,572 KB
testcase_04	AC	87 ms 71,532 KB
testcase_05	AC	90 ms 71,632 KB
testcase_06	AC	88 ms 71,656 KB
testcase_07	AC	86 ms 71,644 KB
testcase_08	AC	87 ms 71,400 KB
testcase_09	AC	89 ms 71,612 KB
testcase_10	AC	88 ms 71,524 KB
testcase_11	AC	89 ms 71,312 KB
testcase_12	AC	88 ms 71,404 KB
testcase_13	AC	87 ms 71,360 KB
testcase_14	AC	86 ms 71,672 KB
testcase_15	AC	87 ms 71,488 KB
testcase_16	AC	86 ms 71,600 KB
testcase_17	AC	88 ms 71,412 KB
testcase_18	AC	86 ms 71,316 KB
testcase_19	AC	85 ms 71,372 KB
testcase_20	AC	89 ms 71,608 KB
testcase_21	AC	86 ms 71,652 KB
testcase_22	AC	85 ms 71,612 KB
testcase_23	AC	87 ms 71,600 KB
testcase_24	AC	87 ms 71,536 KB
testcase_25	AC	87 ms 71,160 KB
testcase_26	AC	87 ms 71,528 KB
testcase_27	AC	87 ms 71,528 KB
testcase_28	AC	89 ms 71,612 KB
testcase_29	AC	86 ms 71,608 KB
testcase_30	AC	93 ms 71,648 KB
testcase_31	AC	93 ms 71,592 KB
testcase_32	AC	93 ms 71,572 KB
testcase_33	AC	91 ms 71,568 KB
testcase_34	AC	89 ms 71,484 KB
testcase_35	AC	92 ms 71,588 KB
testcase_36	AC	88 ms 71,568 KB
testcase_37	AC	88 ms 71,508 KB
testcase_38	AC	86 ms 71,572 KB
testcase_39	AC	91 ms 71,532 KB
testcase_40	AC	86 ms 71,528 KB
testcase_41	AC	88 ms 71,600 KB
testcase_42	AC	88 ms 71,716 KB
testcase_43	AC	114 ms 77,020 KB
testcase_44	AC	93 ms 76,836 KB
testcase_45	AC	96 ms 77,204 KB
testcase_46	AC	102 ms 76,688 KB
testcase_47	AC	96 ms 76,276 KB
testcase_48	AC	100 ms 76,648 KB
testcase_49	AC	89 ms 71,676 KB
testcase_50	AC	106 ms 77,320 KB
testcase_51	AC	106 ms 76,872 KB
testcase_52	AC	108 ms 76,960 KB
testcase_53	AC	102 ms 76,932 KB
testcase_54	AC	107 ms 77,040 KB
testcase_55	AC	102 ms 76,912 KB
testcase_56	AC	89 ms 71,404 KB
testcase_57	AC	102 ms 76,752 KB
testcase_58	AC	102 ms 76,776 KB
testcase_59	AC	87 ms 71,628 KB
testcase_60	AC	95 ms 76,292 KB
testcase_61	AC	102 ms 77,296 KB
testcase_62	AC	90 ms 71,608 KB
testcase_63	AC	140 ms 78,376 KB
testcase_64	AC	118 ms 77,908 KB
testcase_65	AC	122 ms 78,464 KB
testcase_66	AC	123 ms 78,460 KB
testcase_67	AC	115 ms 77,864 KB
testcase_68	AC	125 ms 78,616 KB
testcase_69	AC	125 ms 77,840 KB
testcase_70	AC	120 ms 78,436 KB
testcase_71	AC	120 ms 78,392 KB
testcase_72	AC	125 ms 78,612 KB
testcase_73	AC	118 ms 78,344 KB
testcase_74	AC	126 ms 78,560 KB
testcase_75	AC	121 ms 77,832 KB
testcase_76	AC	109 ms 77,816 KB
testcase_77	AC	123 ms 78,396 KB
testcase_78	AC	138 ms 80,176 KB
testcase_79	AC	125 ms 78,184 KB
testcase_80	AC	128 ms 78,400 KB
testcase_81	AC	124 ms 78,408 KB
testcase_82	AC	141 ms 80,104 KB
testcase_83	AC	304 ms 99,392 KB
testcase_84	AC	275 ms 98,888 KB
testcase_85	AC	212 ms 90,920 KB
testcase_86	AC	252 ms 96,140 KB
testcase_87	AC	274 ms 97,564 KB
testcase_88	AC	138 ms 81,068 KB
testcase_89	AC	292 ms 99,528 KB
testcase_90	AC	221 ms 91,708 KB
testcase_91	AC	194 ms 89,020 KB
testcase_92	AC	160 ms 84,180 KB
testcase_93	AC	259 ms 95,216 KB
testcase_94	AC	245 ms 93,428 KB
testcase_95	AC	244 ms 93,392 KB
testcase_96	AC	287 ms 98,124 KB
testcase_97	AC	190 ms 87,364 KB
testcase_98	AC	290 ms 98,348 KB
testcase_99	AC	214 ms 90,768 KB
testcase_100	AC	317 ms 99,944 KB
testcase_101	AC	158 ms 83,408 KB
testcase_102	AC	138 ms 80,664 KB
testcase_103	AC	150 ms 83,872 KB
testcase_104	AC	167 ms 84,804 KB
testcase_105	AC	260 ms 95,396 KB
testcase_106	AC	187 ms 88,640 KB
testcase_107	AC	295 ms 99,096 KB
testcase_108	AC	296 ms 98,740 KB
testcase_109	AC	246 ms 94,760 KB
testcase_110	AC	236 ms 93,164 KB
testcase_111	AC	250 ms 94,272 KB
testcase_112	AC	165 ms 84,676 KB
testcase_113	AC	230 ms 92,308 KB
testcase_114	AC	197 ms 88,028 KB
testcase_115	AC	140 ms 81,380 KB
testcase_116	AC	202 ms 89,996 KB
testcase_117	AC	171 ms 84,784 KB
testcase_118	AC	281 ms 97,704 KB
testcase_119	AC	212 ms 90,152 KB
testcase_120	AC	281 ms 97,440 KB
testcase_121	AC	157 ms 84,304 KB
testcase_122	AC	197 ms 89,392 KB
testcase_123	AC	89 ms 71,592 KB
testcase_124	AC	364 ms 110,748 KB
testcase_125	AC	362 ms 110,508 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import sys
input = sys.stdin.readline
from collections import deque
class UnDirectedGraph:
  def __init__(self, N):
    self.V = N
    self.edge = [[] for _ in range(self.V)]
    self.edges = [0]*N
    self.visited = [False]*N
    self.parent = [N]*N
    self.order = [N]*N
    self.low = [N]*N
  
  def add_edges(self, M):
    for i in range(M):
      a,b = map(int, input().split())
      self.edge[a-1].append((b-1,i))
      self.edge[b-1].append((a-1,i))
      self.edges[i] = (a-1,b-1)

  def add_edge(self, a, b):
    self.edge[a].append(b)
    self.edge[b].append(a)

  def low_link(self, start):
    stack = deque([start])
    self.parent[start] = -1
    #記録したい値の配列を定義
    self.order[start] = 0
    cnt = 1
    while stack:
      v = stack[-1]
      for u,i in self.edge[v]:
        if u==self.parent[v]:
          pass
        elif self.order[u]<self.order[v]:
          self.low[v] = min(self.low[v], self.order[u])
        elif self.parent[u]==N: #行き
          self.parent[u] = v
          self.order[u] = cnt
          self.low[u] = cnt
          stack.append(u)
          cnt += 1
          break
        else:
          self.low[v] = min(self.low[v], self.low[u])
      else:
        stack.pop() #帰り
    return

N = int(input())
G = UnDirectedGraph(N)
G.add_edges(N)
G.low_link(0)
ans = []
for i,(a,b) in enumerate(G.edges):
  if G.order[a]>G.order[b]:
    a,b = b,a
  if G.low[b]<=G.order[a]:
    ans.append(i+1)
print(len(ans))
print(*ans)

yukicoder

結果

テストケース

ソースコード