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

提出ソース

結果

問題	No.1254 補強への架け橋
ユーザー	roaris
提出日時	2020-11-15 12:45:18
言語	PyPy3 (7.3.15)
結果	AC
実行時間	551 ms / 2,000 ms
コード長	1,068 bytes
コンパイル時間	271 ms
コンパイル使用メモリ	86,912 KB
実行使用メモリ	189,540 KB
最終ジャッジ日時	2023-09-30 06:55:47
合計ジャッジ時間	29,674 ms
ジャッジサーバーID （参考情報）	judge15 / judge12

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	97 ms 71,556 KB
testcase_01	AC	99 ms 71,544 KB
testcase_02	AC	99 ms 71,620 KB
testcase_03	AC	100 ms 71,192 KB
testcase_04	AC	101 ms 71,592 KB
testcase_05	AC	98 ms 71,500 KB
testcase_06	AC	96 ms 71,172 KB
testcase_07	AC	98 ms 71,200 KB
testcase_08	AC	97 ms 71,420 KB
testcase_09	AC	97 ms 71,548 KB
testcase_10	AC	98 ms 71,196 KB
testcase_11	AC	98 ms 71,712 KB
testcase_12	AC	100 ms 71,596 KB
testcase_13	AC	98 ms 71,568 KB
testcase_14	AC	98 ms 71,416 KB
testcase_15	AC	99 ms 71,568 KB
testcase_16	AC	97 ms 71,496 KB
testcase_17	AC	99 ms 71,620 KB
testcase_18	AC	100 ms 71,332 KB
testcase_19	AC	99 ms 71,384 KB
testcase_20	AC	100 ms 71,432 KB
testcase_21	AC	98 ms 71,572 KB
testcase_22	AC	99 ms 71,196 KB
testcase_23	AC	100 ms 71,204 KB
testcase_24	AC	100 ms 71,552 KB
testcase_25	AC	99 ms 71,428 KB
testcase_26	AC	100 ms 71,512 KB
testcase_27	AC	99 ms 71,380 KB
testcase_28	AC	101 ms 71,380 KB
testcase_29	AC	100 ms 71,204 KB
testcase_30	AC	100 ms 71,544 KB
testcase_31	AC	101 ms 71,584 KB
testcase_32	AC	105 ms 71,608 KB
testcase_33	AC	98 ms 71,380 KB
testcase_34	AC	100 ms 71,196 KB
testcase_35	AC	100 ms 71,608 KB
testcase_36	AC	101 ms 71,636 KB
testcase_37	AC	100 ms 71,656 KB
testcase_38	AC	100 ms 71,700 KB
testcase_39	AC	99 ms 71,324 KB
testcase_40	AC	99 ms 71,544 KB
testcase_41	AC	100 ms 71,412 KB
testcase_42	AC	103 ms 71,204 KB
testcase_43	AC	108 ms 72,072 KB
testcase_44	AC	103 ms 71,612 KB
testcase_45	AC	102 ms 71,568 KB
testcase_46	AC	106 ms 72,120 KB
testcase_47	AC	105 ms 72,348 KB
testcase_48	AC	105 ms 72,108 KB
testcase_49	AC	101 ms 71,416 KB
testcase_50	AC	109 ms 76,316 KB
testcase_51	AC	105 ms 72,312 KB
testcase_52	AC	107 ms 76,260 KB
testcase_53	AC	105 ms 72,096 KB
testcase_54	AC	106 ms 71,916 KB
testcase_55	AC	110 ms 75,924 KB
testcase_56	AC	100 ms 71,620 KB
testcase_57	AC	105 ms 72,072 KB
testcase_58	AC	104 ms 72,100 KB
testcase_59	AC	101 ms 71,500 KB
testcase_60	AC	100 ms 71,412 KB
testcase_61	AC	106 ms 72,072 KB
testcase_62	AC	101 ms 71,368 KB
testcase_63	AC	162 ms 81,308 KB
testcase_64	AC	124 ms 77,672 KB
testcase_65	AC	158 ms 80,860 KB
testcase_66	AC	164 ms 80,708 KB
testcase_67	AC	125 ms 77,564 KB
testcase_68	AC	149 ms 80,640 KB
testcase_69	AC	161 ms 80,748 KB
testcase_70	AC	127 ms 77,836 KB
testcase_71	AC	127 ms 77,876 KB
testcase_72	AC	155 ms 80,960 KB
testcase_73	AC	124 ms 77,736 KB
testcase_74	AC	160 ms 80,220 KB
testcase_75	AC	150 ms 80,272 KB
testcase_76	AC	112 ms 77,560 KB
testcase_77	AC	148 ms 80,476 KB
testcase_78	AC	172 ms 81,324 KB
testcase_79	AC	157 ms 80,864 KB
testcase_80	AC	160 ms 80,796 KB
testcase_81	AC	154 ms 81,120 KB
testcase_82	AC	158 ms 80,696 KB
testcase_83	AC	343 ms 107,148 KB
testcase_84	AC	315 ms 105,008 KB
testcase_85	AC	230 ms 97,128 KB
testcase_86	AC	293 ms 101,012 KB
testcase_87	AC	289 ms 103,420 KB
testcase_88	AC	169 ms 82,312 KB
testcase_89	AC	308 ms 107,112 KB
testcase_90	AC	243 ms 97,212 KB
testcase_91	AC	231 ms 96,136 KB
testcase_92	AC	179 ms 84,576 KB
testcase_93	AC	261 ms 99,568 KB
testcase_94	AC	275 ms 97,916 KB
testcase_95	AC	281 ms 98,128 KB
testcase_96	AC	324 ms 103,944 KB
testcase_97	AC	215 ms 92,080 KB
testcase_98	AC	297 ms 104,188 KB
testcase_99	AC	240 ms 97,220 KB
testcase_100	AC	293 ms 106,324 KB
testcase_101	AC	191 ms 85,580 KB
testcase_102	AC	166 ms 81,684 KB
testcase_103	AC	180 ms 84,272 KB
testcase_104	AC	203 ms 89,112 KB
testcase_105	AC	273 ms 99,896 KB
testcase_106	AC	217 ms 94,248 KB
testcase_107	AC	325 ms 107,136 KB
testcase_108	AC	308 ms 107,100 KB
testcase_109	AC	285 ms 100,512 KB
testcase_110	AC	242 ms 97,992 KB
testcase_111	AC	288 ms 97,908 KB
testcase_112	AC	208 ms 88,620 KB
testcase_113	AC	272 ms 97,960 KB
testcase_114	AC	226 ms 92,620 KB
testcase_115	AC	169 ms 82,516 KB
testcase_116	AC	240 ms 96,268 KB
testcase_117	AC	206 ms 89,520 KB
testcase_118	AC	288 ms 103,880 KB
testcase_119	AC	250 ms 98,068 KB
testcase_120	AC	299 ms 103,764 KB
testcase_121	AC	192 ms 86,416 KB
testcase_122	AC	217 ms 95,700 KB
testcase_123	AC	98 ms 71,616 KB
testcase_124	AC	551 ms 189,540 KB
testcase_125	AC	541 ms 189,380 KB

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

ソースコード

raw source code

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5+10)
from collections import *

def dfs(v, pv):
    global pos
    
    seen[v] = True
    hist.append(v)
    
    for nv in G[v]:
        if nv==pv:
            continue
        
        if finished[nv]:
            continue
        
        if seen[nv] and not finished[nv]:
            pos = nv
            return
        
        dfs(nv, v)
        
        if pos!=-1:
            return
    
    hist.pop()
    finished[v] = True

N = int(input())
G = [[] for _ in range(N)]
edges = defaultdict(int)

for i in range(N):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
    edges[(min(a-1, b-1), max(a-1, b-1))] = i

pos = -1
seen = [False]*N
finished = [False]*N
hist = []
dfs(0, -1)
cycle = []

while hist:
    cycle.append(hist.pop())
    
    if cycle[-1]==pos:
        break
    
ans = []

for i in range(len(cycle)):
    u, v = cycle[i], cycle[(i+1)%len(cycle)]
    u, v = min(u, v), max(u, v)
    ans.append(edges[(u, v)]+1)
    
print(len(ans))
print(*ans)

yukicoder

結果

テストケース

ソースコード