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

提出ソース

結果

問題	No.1254 補強への架け橋
ユーザー	titia
提出日時	2020-10-10 01:01:00
言語	PyPy3 (7.3.15)
結果	AC
実行時間	339 ms / 2,000 ms
コード長	968 bytes
コンパイル時間	254 ms
コンパイル使用メモリ	87,032 KB
実行使用メモリ	145,468 KB
最終ジャッジ日時	2023-09-27 20:33:18
合計ジャッジ時間	22,158 ms
ジャッジサーバーID （参考情報）	judge15 / judge14

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	66 ms 71,232 KB
testcase_01	AC	68 ms 71,144 KB
testcase_02	AC	67 ms 71,380 KB
testcase_03	AC	68 ms 71,124 KB
testcase_04	AC	65 ms 71,368 KB
testcase_05	AC	68 ms 71,328 KB
testcase_06	AC	70 ms 71,264 KB
testcase_07	AC	65 ms 71,076 KB
testcase_08	AC	67 ms 71,312 KB
testcase_09	AC	67 ms 71,316 KB
testcase_10	AC	65 ms 71,208 KB
testcase_11	AC	64 ms 71,248 KB
testcase_12	AC	67 ms 71,180 KB
testcase_13	AC	67 ms 71,372 KB
testcase_14	AC	67 ms 71,332 KB
testcase_15	AC	69 ms 71,052 KB
testcase_16	AC	67 ms 71,484 KB
testcase_17	AC	67 ms 71,076 KB
testcase_18	AC	66 ms 71,448 KB
testcase_19	AC	68 ms 71,276 KB
testcase_20	AC	67 ms 71,236 KB
testcase_21	AC	66 ms 71,208 KB
testcase_22	AC	67 ms 71,316 KB
testcase_23	AC	67 ms 71,304 KB
testcase_24	AC	66 ms 71,296 KB
testcase_25	AC	66 ms 71,284 KB
testcase_26	AC	68 ms 71,488 KB
testcase_27	AC	68 ms 71,312 KB
testcase_28	AC	69 ms 71,316 KB
testcase_29	AC	67 ms 71,296 KB
testcase_30	AC	66 ms 71,248 KB
testcase_31	AC	67 ms 71,208 KB
testcase_32	AC	68 ms 71,320 KB
testcase_33	AC	69 ms 71,312 KB
testcase_34	AC	73 ms 71,156 KB
testcase_35	AC	68 ms 71,316 KB
testcase_36	AC	66 ms 71,320 KB
testcase_37	AC	68 ms 71,252 KB
testcase_38	AC	68 ms 71,276 KB
testcase_39	AC	67 ms 71,316 KB
testcase_40	AC	68 ms 71,384 KB
testcase_41	AC	68 ms 71,084 KB
testcase_42	AC	68 ms 71,316 KB
testcase_43	AC	85 ms 76,272 KB
testcase_44	AC	74 ms 75,828 KB
testcase_45	AC	73 ms 75,564 KB
testcase_46	AC	80 ms 75,736 KB
testcase_47	AC	77 ms 75,924 KB
testcase_48	AC	80 ms 75,752 KB
testcase_49	AC	68 ms 71,424 KB
testcase_50	AC	81 ms 75,964 KB
testcase_51	AC	80 ms 76,116 KB
testcase_52	AC	83 ms 76,192 KB
testcase_53	AC	82 ms 76,396 KB
testcase_54	AC	82 ms 76,124 KB
testcase_55	AC	81 ms 76,000 KB
testcase_56	AC	69 ms 71,364 KB
testcase_57	AC	77 ms 75,812 KB
testcase_58	AC	76 ms 75,712 KB
testcase_59	AC	67 ms 71,476 KB
testcase_60	AC	76 ms 75,608 KB
testcase_61	AC	83 ms 76,368 KB
testcase_62	AC	69 ms 71,324 KB
testcase_63	AC	116 ms 78,088 KB
testcase_64	AC	108 ms 78,448 KB
testcase_65	AC	111 ms 78,180 KB
testcase_66	AC	116 ms 78,196 KB
testcase_67	AC	105 ms 77,972 KB
testcase_68	AC	110 ms 78,340 KB
testcase_69	AC	117 ms 78,096 KB
testcase_70	AC	106 ms 78,140 KB
testcase_71	AC	103 ms 77,996 KB
testcase_72	AC	116 ms 78,172 KB
testcase_73	AC	102 ms 77,968 KB
testcase_74	AC	108 ms 78,160 KB
testcase_75	AC	109 ms 78,184 KB
testcase_76	AC	97 ms 77,068 KB
testcase_77	AC	112 ms 78,152 KB
testcase_78	AC	105 ms 78,048 KB
testcase_79	AC	116 ms 78,212 KB
testcase_80	AC	111 ms 78,084 KB
testcase_81	AC	111 ms 78,064 KB
testcase_82	AC	114 ms 78,232 KB
testcase_83	AC	226 ms 98,124 KB
testcase_84	AC	215 ms 97,812 KB
testcase_85	AC	165 ms 89,960 KB
testcase_86	AC	197 ms 94,748 KB
testcase_87	AC	220 ms 96,428 KB
testcase_88	AC	121 ms 80,592 KB
testcase_89	AC	212 ms 97,812 KB
testcase_90	AC	171 ms 90,588 KB
testcase_91	AC	168 ms 87,748 KB
testcase_92	AC	130 ms 80,288 KB
testcase_93	AC	191 ms 94,056 KB
testcase_94	AC	180 ms 92,408 KB
testcase_95	AC	180 ms 92,148 KB
testcase_96	AC	216 ms 96,952 KB
testcase_97	AC	157 ms 86,500 KB
testcase_98	AC	217 ms 97,072 KB
testcase_99	AC	176 ms 89,620 KB
testcase_100	AC	221 ms 98,160 KB
testcase_101	AC	129 ms 80,592 KB
testcase_102	AC	112 ms 78,224 KB
testcase_103	AC	126 ms 80,684 KB
testcase_104	AC	142 ms 85,132 KB
testcase_105	AC	197 ms 93,872 KB
testcase_106	AC	163 ms 87,124 KB
testcase_107	AC	215 ms 97,892 KB
testcase_108	AC	220 ms 97,652 KB
testcase_109	AC	195 ms 93,764 KB
testcase_110	AC	188 ms 92,124 KB
testcase_111	AC	186 ms 93,104 KB
testcase_112	AC	135 ms 84,600 KB
testcase_113	AC	181 ms 91,900 KB
testcase_114	AC	154 ms 86,952 KB
testcase_115	AC	126 ms 81,040 KB
testcase_116	AC	154 ms 88,272 KB
testcase_117	AC	141 ms 84,748 KB
testcase_118	AC	216 ms 96,780 KB
testcase_119	AC	167 ms 89,224 KB
testcase_120	AC	202 ms 95,904 KB
testcase_121	AC	134 ms 83,416 KB
testcase_122	AC	161 ms 88,360 KB
testcase_123	AC	65 ms 71,176 KB
testcase_124	AC	339 ms 145,348 KB
testcase_125	AC	332 ms 145,468 KB

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

ソースコード

raw source code

N=int(input())
EDGE=[tuple(map(int,input().split())) for i in range(N)]

E=[[] for i in range(N+1)]

for x,y in EDGE:
    E[x].append(y)
    E[y].append(x)

Q=[(1,N+5)]
USE=[0]*(N+1)
FR=[-1]*(N+1)
USE[1]=1

while Q:
    x,fr=Q.pop()
    ANS=-1

    for to in E[x]:
        if fr==to:
            continue
        if USE[to]==0:
            USE[to]=1
            FR[to]=x
            Q.append((to,x))
        else:
            ANS=to
            NOW=x
            break
    if ANS!=-1:
        break

LIST0=[]
LIST1=[]

while NOW!=1:
    LIST0.append(NOW)
    NOW=FR[NOW]

while ANS!=1:
    LIST1.append(ANS)
    ANS=FR[ANS]

LIST0.append(1)
LIST1.append(1)

while LIST0[-1]==LIST1[-1]:
    x=LIST0.pop()
    y=LIST1.pop()

LIST=[x]+LIST0[::-1]+LIST1

SET=set()
for i in range(len(LIST)):
    x=LIST[i-1]
    y=LIST[i]
    SET.add((x,y))
    SET.add((y,x))

ALIST=[]
for i in range(N):
    if EDGE[i] in SET:
        ALIST.append(i+1)

print(len(ALIST))
print(*ALIST)

yukicoder

結果

テストケース

ソースコード