#710951 (Python3) No.1254 補強への架け橋

提出ソース

結果

問題	No.1254 補強への架け橋
ユーザー	mkawa2
提出日時	2021-10-29 14:57:04
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	AC
実行時間	669 ms / 2,000 ms
コード長	1,571 bytes
コンパイル時間	213 ms
コンパイル使用メモリ	12,800 KB
実行使用メモリ	60,984 KB
最終ジャッジ日時	2024-10-07 08:34:25
合計ジャッジ時間	24,320 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	29 ms 10,752 KB
testcase_01	AC	27 ms 10,752 KB
testcase_02	AC	27 ms 10,752 KB
testcase_03	AC	28 ms 10,752 KB
testcase_04	AC	27 ms 10,752 KB
testcase_05	AC	27 ms 10,880 KB
testcase_06	AC	28 ms 10,752 KB
testcase_07	AC	28 ms 10,752 KB
testcase_08	AC	28 ms 10,752 KB
testcase_09	AC	27 ms 10,752 KB
testcase_10	AC	27 ms 10,752 KB
testcase_11	AC	26 ms 10,880 KB
testcase_12	AC	27 ms 10,880 KB
testcase_13	AC	26 ms 10,752 KB
testcase_14	AC	27 ms 10,752 KB
testcase_15	AC	31 ms 10,752 KB
testcase_16	AC	28 ms 10,880 KB
testcase_17	AC	27 ms 10,752 KB
testcase_18	AC	28 ms 10,752 KB
testcase_19	AC	27 ms 10,752 KB
testcase_20	AC	27 ms 10,752 KB
testcase_21	AC	27 ms 10,752 KB
testcase_22	AC	27 ms 10,752 KB
testcase_23	AC	26 ms 10,624 KB
testcase_24	AC	28 ms 10,624 KB
testcase_25	AC	27 ms 10,752 KB
testcase_26	AC	27 ms 10,752 KB
testcase_27	AC	26 ms 10,880 KB
testcase_28	AC	26 ms 10,752 KB
testcase_29	AC	27 ms 10,752 KB
testcase_30	AC	27 ms 10,880 KB
testcase_31	AC	27 ms 10,624 KB
testcase_32	AC	28 ms 10,752 KB
testcase_33	AC	27 ms 10,880 KB
testcase_34	AC	26 ms 10,880 KB
testcase_35	AC	27 ms 10,880 KB
testcase_36	AC	26 ms 10,752 KB
testcase_37	AC	28 ms 10,880 KB
testcase_38	AC	26 ms 10,624 KB
testcase_39	AC	27 ms 10,752 KB
testcase_40	AC	26 ms 10,880 KB
testcase_41	AC	27 ms 10,880 KB
testcase_42	AC	27 ms 10,752 KB
testcase_43	AC	30 ms 11,136 KB
testcase_44	AC	29 ms 11,136 KB
testcase_45	AC	29 ms 10,880 KB
testcase_46	AC	30 ms 11,136 KB
testcase_47	AC	29 ms 10,880 KB
testcase_48	AC	30 ms 10,880 KB
testcase_49	AC	28 ms 10,624 KB
testcase_50	AC	30 ms 11,136 KB
testcase_51	AC	30 ms 11,136 KB
testcase_52	AC	30 ms 11,136 KB
testcase_53	AC	30 ms 11,136 KB
testcase_54	AC	31 ms 11,008 KB
testcase_55	AC	30 ms 11,264 KB
testcase_56	AC	28 ms 11,008 KB
testcase_57	AC	30 ms 11,136 KB
testcase_58	AC	30 ms 11,008 KB
testcase_59	AC	28 ms 10,752 KB
testcase_60	AC	29 ms 10,752 KB
testcase_61	AC	29 ms 11,136 KB
testcase_62	AC	27 ms 10,752 KB
testcase_63	AC	67 ms 14,656 KB
testcase_64	AC	35 ms 11,904 KB
testcase_65	AC	47 ms 13,548 KB
testcase_66	AC	43 ms 12,800 KB
testcase_67	AC	36 ms 11,520 KB
testcase_68	AC	48 ms 13,824 KB
testcase_69	AC	51 ms 13,804 KB
testcase_70	AC	38 ms 12,160 KB
testcase_71	AC	36 ms 11,776 KB
testcase_72	AC	53 ms 13,692 KB
testcase_73	AC	36 ms 12,032 KB
testcase_74	AC	48 ms 13,656 KB
testcase_75	AC	47 ms 12,672 KB
testcase_76	AC	33 ms 11,264 KB
testcase_77	AC	42 ms 12,672 KB
testcase_78	AC	57 ms 14,448 KB
testcase_79	AC	58 ms 14,468 KB
testcase_80	AC	52 ms 13,996 KB
testcase_81	AC	60 ms 14,480 KB
testcase_82	AC	55 ms 14,168 KB
testcase_83	AC	462 ms 54,996 KB
testcase_84	AC	419 ms 54,668 KB
testcase_85	AC	236 ms 35,368 KB
testcase_86	AC	335 ms 42,792 KB
testcase_87	AC	383 ms 45,212 KB
testcase_88	AC	76 ms 16,916 KB
testcase_89	AC	409 ms 54,820 KB
testcase_90	AC	270 ms 36,248 KB
testcase_91	AC	217 ms 33,100 KB
testcase_92	AC	115 ms 22,028 KB
testcase_93	AC	311 ms 41,132 KB
testcase_94	AC	275 ms 38,920 KB
testcase_95	AC	290 ms 38,772 KB
testcase_96	AC	368 ms 54,556 KB
testcase_97	AC	175 ms 27,072 KB
testcase_98	AC	430 ms 54,620 KB
testcase_99	AC	255 ms 34,420 KB
testcase_100	AC	449 ms 55,268 KB
testcase_101	AC	113 ms 21,948 KB
testcase_102	AC	72 ms 16,496 KB
testcase_103	AC	115 ms 22,136 KB
testcase_104	AC	155 ms 25,184 KB
testcase_105	AC	338 ms 41,260 KB
testcase_106	AC	198 ms 32,856 KB
testcase_107	AC	401 ms 54,960 KB
testcase_108	AC	460 ms 54,976 KB
testcase_109	AC	304 ms 41,184 KB
testcase_110	AC	297 ms 38,464 KB
testcase_111	AC	296 ms 40,248 KB
testcase_112	AC	142 ms 24,376 KB
testcase_113	AC	295 ms 37,932 KB
testcase_114	AC	182 ms 27,752 KB
testcase_115	AC	77 ms 17,152 KB
testcase_116	AC	206 ms 33,044 KB
testcase_117	AC	142 ms 24,272 KB
testcase_118	AC	384 ms 54,412 KB
testcase_119	AC	230 ms 34,224 KB
testcase_120	AC	384 ms 44,844 KB
testcase_121	AC	130 ms 22,860 KB
testcase_122	AC	235 ms 33,056 KB
testcase_123	AC	27 ms 11,008 KB
testcase_124	AC	669 ms 60,984 KB
testcase_125	AC	663 ms 60,984 KB

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

ソースコード

raw source code

import sys

# sys.setrecursionlimit(200005)
int1 = lambda x: int(x)-1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]
def SI(): return sys.stdin.readline().rstrip()
# dij = [(0, 1), (-1, 0), (0, -1), (1, 0)]
dij = [(0, 1), (1, 0), (0, -1), (-1, 0)]
# dij = [(0, 1), (-1, 0), (0, -1), (1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
inf = 1 << 63
# md = 998244353
md = 10**9+7

def dfs(to, root=0):
    n = len(to)
    par = [-1]*n
    go = [True]*n
    stack = [root]
    loop = -1
    while stack:
        u = stack.pop()

        if go[u]:
            go[u] = False
            stack.append(u)
            # toの変数注意
            for v in to[u]:
                if v == par[u]: continue
                if not go[v]:
                    return v, u, par
                stack.append(v)
                par[v] = u

        else:
            # toの変数注意
            for v in to[u]:
                if v == par[u]: continue

n = II()
to = [[] for _ in range(n)]
uvtoi = {}
for i in range(n):
    u, v = LI1()
    to[u].append(v)
    to[v].append(u)
    uvtoi[u, v] = uvtoi[v, u] = i

p, u, par = dfs(to, 0)
uu = [p, u]
while uu[-1] != p:
    v = par[uu[-1]]
    uu.append(v)

ans = []
for u, v in zip(uu, uu[1:]):
    ans.append(uvtoi[u, v]+1)

print(len(ans))
print(*ans)

yukicoder

結果

テストケース

ソースコード