#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
実行時間	818 ms / 2,000 ms
コード長	1,571 bytes
コンパイル時間	242 ms
コンパイル使用メモリ	13,056 KB
実行使用メモリ	61,112 KB
最終ジャッジ日時	2024-04-16 13:22:59
合計ジャッジ時間	27,722 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	31 ms 10,880 KB
testcase_01	AC	34 ms 10,752 KB
testcase_02	AC	32 ms 10,752 KB
testcase_03	AC	31 ms 11,008 KB
testcase_04	AC	31 ms 10,880 KB
testcase_05	AC	32 ms 10,752 KB
testcase_06	AC	31 ms 11,008 KB
testcase_07	AC	33 ms 10,752 KB
testcase_08	AC	31 ms 10,880 KB
testcase_09	AC	31 ms 11,008 KB
testcase_10	AC	32 ms 10,880 KB
testcase_11	AC	31 ms 11,008 KB
testcase_12	AC	32 ms 10,752 KB
testcase_13	AC	32 ms 10,880 KB
testcase_14	AC	31 ms 10,880 KB
testcase_15	AC	31 ms 10,880 KB
testcase_16	AC	31 ms 10,880 KB
testcase_17	AC	31 ms 11,008 KB
testcase_18	AC	31 ms 10,752 KB
testcase_19	AC	31 ms 10,880 KB
testcase_20	AC	31 ms 10,880 KB
testcase_21	AC	32 ms 10,880 KB
testcase_22	AC	32 ms 11,008 KB
testcase_23	AC	32 ms 10,880 KB
testcase_24	AC	31 ms 10,880 KB
testcase_25	AC	32 ms 10,880 KB
testcase_26	AC	31 ms 10,752 KB
testcase_27	AC	31 ms 10,880 KB
testcase_28	AC	31 ms 10,880 KB
testcase_29	AC	31 ms 11,008 KB
testcase_30	AC	33 ms 10,880 KB
testcase_31	AC	32 ms 11,008 KB
testcase_32	AC	31 ms 10,880 KB
testcase_33	AC	32 ms 11,008 KB
testcase_34	AC	31 ms 10,880 KB
testcase_35	AC	33 ms 10,880 KB
testcase_36	AC	31 ms 10,752 KB
testcase_37	AC	32 ms 10,752 KB
testcase_38	AC	31 ms 10,752 KB
testcase_39	AC	32 ms 10,752 KB
testcase_40	AC	32 ms 10,752 KB
testcase_41	AC	32 ms 10,880 KB
testcase_42	AC	32 ms 10,880 KB
testcase_43	AC	36 ms 11,264 KB
testcase_44	AC	32 ms 11,008 KB
testcase_45	AC	32 ms 11,136 KB
testcase_46	AC	35 ms 11,264 KB
testcase_47	AC	33 ms 11,008 KB
testcase_48	AC	33 ms 11,008 KB
testcase_49	AC	32 ms 11,008 KB
testcase_50	AC	34 ms 11,264 KB
testcase_51	AC	35 ms 11,392 KB
testcase_52	AC	36 ms 11,264 KB
testcase_53	AC	36 ms 11,264 KB
testcase_54	AC	35 ms 11,136 KB
testcase_55	AC	34 ms 11,264 KB
testcase_56	AC	32 ms 10,880 KB
testcase_57	AC	37 ms 11,136 KB
testcase_58	AC	39 ms 11,008 KB
testcase_59	AC	31 ms 10,880 KB
testcase_60	AC	32 ms 10,880 KB
testcase_61	AC	34 ms 11,264 KB
testcase_62	AC	31 ms 10,752 KB
testcase_63	AC	71 ms 14,784 KB
testcase_64	AC	42 ms 11,904 KB
testcase_65	AC	56 ms 13,676 KB
testcase_66	AC	50 ms 13,056 KB
testcase_67	AC	39 ms 11,776 KB
testcase_68	AC	54 ms 13,696 KB
testcase_69	AC	60 ms 13,808 KB
testcase_70	AC	45 ms 12,160 KB
testcase_71	AC	41 ms 12,032 KB
testcase_72	AC	60 ms 13,952 KB
testcase_73	AC	43 ms 12,288 KB
testcase_74	AC	57 ms 13,656 KB
testcase_75	AC	51 ms 12,800 KB
testcase_76	AC	36 ms 11,520 KB
testcase_77	AC	49 ms 12,672 KB
testcase_78	AC	63 ms 14,448 KB
testcase_79	AC	66 ms 14,600 KB
testcase_80	AC	60 ms 14,124 KB
testcase_81	AC	69 ms 14,472 KB
testcase_82	AC	63 ms 14,300 KB
testcase_83	AC	558 ms 55,128 KB
testcase_84	AC	495 ms 54,920 KB
testcase_85	AC	285 ms 35,236 KB
testcase_86	AC	423 ms 42,856 KB
testcase_87	AC	478 ms 45,088 KB
testcase_88	AC	87 ms 16,912 KB
testcase_89	AC	509 ms 55,076 KB
testcase_90	AC	332 ms 36,252 KB
testcase_91	AC	282 ms 32,968 KB
testcase_92	AC	147 ms 22,028 KB
testcase_93	AC	390 ms 41,264 KB
testcase_94	AC	351 ms 38,920 KB
testcase_95	AC	356 ms 38,776 KB
testcase_96	AC	464 ms 54,720 KB
testcase_97	AC	227 ms 27,072 KB
testcase_98	AC	524 ms 54,660 KB
testcase_99	AC	312 ms 34,548 KB
testcase_100	AC	511 ms 55,136 KB
testcase_101	AC	125 ms 21,824 KB
testcase_102	AC	80 ms 16,368 KB
testcase_103	AC	136 ms 22,012 KB
testcase_104	AC	177 ms 25,168 KB
testcase_105	AC	412 ms 41,516 KB
testcase_106	AC	249 ms 32,724 KB
testcase_107	AC	483 ms 55,080 KB
testcase_108	AC	528 ms 54,976 KB
testcase_109	AC	382 ms 40,932 KB
testcase_110	AC	370 ms 38,724 KB
testcase_111	AC	366 ms 40,500 KB
testcase_112	AC	178 ms 24,512 KB
testcase_113	AC	366 ms 38,064 KB
testcase_114	AC	217 ms 28,136 KB
testcase_115	AC	93 ms 17,536 KB
testcase_116	AC	270 ms 33,132 KB
testcase_117	AC	181 ms 24,400 KB
testcase_118	AC	456 ms 54,668 KB
testcase_119	AC	287 ms 34,352 KB
testcase_120	AC	474 ms 44,848 KB
testcase_121	AC	156 ms 23,112 KB
testcase_122	AC	298 ms 33,188 KB
testcase_123	AC	33 ms 11,008 KB
testcase_124	AC	818 ms 60,980 KB
testcase_125	AC	816 ms 61,112 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

結果

テストケース

ソースコード