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

提出ソース

結果

問題	No.1254 補強への架け橋
ユーザー	nagiss
提出日時	2020-10-09 23:25:30
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	AC
実行時間	744 ms / 2,000 ms
コード長	1,202 bytes
コンパイル時間	215 ms
コンパイル使用メモリ	12,800 KB
実行使用メモリ	70,792 KB
最終ジャッジ日時	2024-07-20 14:19:54
合計ジャッジ時間	29,335 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	29 ms 10,880 KB
testcase_01	AC	29 ms 10,752 KB
testcase_02	AC	26 ms 10,880 KB
testcase_03	AC	29 ms 11,008 KB
testcase_04	AC	25 ms 10,880 KB
testcase_05	AC	28 ms 10,880 KB
testcase_06	AC	25 ms 10,880 KB
testcase_07	AC	27 ms 10,752 KB
testcase_08	AC	26 ms 10,752 KB
testcase_09	AC	27 ms 10,880 KB
testcase_10	AC	26 ms 10,752 KB
testcase_11	AC	25 ms 10,880 KB
testcase_12	AC	25 ms 10,752 KB
testcase_13	AC	26 ms 10,880 KB
testcase_14	AC	26 ms 10,752 KB
testcase_15	AC	25 ms 10,880 KB
testcase_16	AC	26 ms 10,880 KB
testcase_17	AC	25 ms 10,880 KB
testcase_18	AC	25 ms 10,752 KB
testcase_19	AC	27 ms 10,752 KB
testcase_20	AC	26 ms 10,880 KB
testcase_21	AC	27 ms 10,880 KB
testcase_22	AC	26 ms 10,880 KB
testcase_23	AC	26 ms 10,880 KB
testcase_24	AC	25 ms 11,008 KB
testcase_25	AC	25 ms 10,752 KB
testcase_26	AC	26 ms 10,752 KB
testcase_27	AC	26 ms 10,880 KB
testcase_28	AC	26 ms 10,880 KB
testcase_29	AC	25 ms 10,880 KB
testcase_30	AC	26 ms 10,752 KB
testcase_31	AC	26 ms 10,752 KB
testcase_32	AC	26 ms 10,880 KB
testcase_33	AC	27 ms 10,752 KB
testcase_34	AC	28 ms 10,880 KB
testcase_35	AC	27 ms 10,880 KB
testcase_36	AC	28 ms 10,752 KB
testcase_37	AC	28 ms 10,880 KB
testcase_38	AC	27 ms 10,752 KB
testcase_39	AC	26 ms 10,880 KB
testcase_40	AC	29 ms 10,752 KB
testcase_41	AC	27 ms 10,752 KB
testcase_42	AC	27 ms 10,752 KB
testcase_43	AC	31 ms 11,264 KB
testcase_44	AC	26 ms 10,880 KB
testcase_45	AC	28 ms 10,752 KB
testcase_46	AC	32 ms 11,008 KB
testcase_47	AC	29 ms 10,880 KB
testcase_48	AC	33 ms 11,008 KB
testcase_49	AC	28 ms 10,880 KB
testcase_50	AC	31 ms 11,136 KB
testcase_51	AC	32 ms 11,008 KB
testcase_52	AC	33 ms 11,264 KB
testcase_53	AC	31 ms 11,136 KB
testcase_54	AC	30 ms 11,008 KB
testcase_55	AC	30 ms 11,008 KB
testcase_56	AC	27 ms 10,880 KB
testcase_57	AC	30 ms 11,136 KB
testcase_58	AC	29 ms 11,136 KB
testcase_59	AC	27 ms 10,752 KB
testcase_60	AC	28 ms 10,880 KB
testcase_61	AC	32 ms 11,136 KB
testcase_62	AC	28 ms 10,880 KB
testcase_63	AC	82 ms 15,228 KB
testcase_64	AC	45 ms 11,904 KB
testcase_65	AC	60 ms 13,952 KB
testcase_66	AC	54 ms 13,440 KB
testcase_67	AC	35 ms 11,648 KB
testcase_68	AC	57 ms 13,696 KB
testcase_69	AC	73 ms 14,336 KB
testcase_70	AC	48 ms 12,288 KB
testcase_71	AC	40 ms 11,776 KB
testcase_72	AC	69 ms 14,336 KB
testcase_73	AC	42 ms 12,032 KB
testcase_74	AC	65 ms 14,208 KB
testcase_75	AC	54 ms 13,696 KB
testcase_76	AC	33 ms 11,136 KB
testcase_77	AC	49 ms 12,672 KB
testcase_78	AC	71 ms 14,976 KB
testcase_79	AC	79 ms 15,104 KB
testcase_80	AC	72 ms 14,720 KB
testcase_81	AC	79 ms 14,976 KB
testcase_82	AC	73 ms 14,720 KB
testcase_83	AC	687 ms 57,356 KB
testcase_84	AC	701 ms 56,476 KB
testcase_85	AC	396 ms 37,292 KB
testcase_86	AC	547 ms 49,244 KB
testcase_87	AC	630 ms 51,364 KB
testcase_88	AC	104 ms 17,100 KB
testcase_89	AC	668 ms 57,020 KB
testcase_90	AC	413 ms 38,316 KB
testcase_91	AC	324 ms 33,708 KB
testcase_92	AC	169 ms 24,148 KB
testcase_93	AC	524 ms 43,820 KB
testcase_94	AC	489 ms 41,224 KB
testcase_95	AC	491 ms 41,088 KB
testcase_96	AC	654 ms 55,360 KB
testcase_97	AC	284 ms 29,712 KB
testcase_98	AC	640 ms 55,720 KB
testcase_99	AC	405 ms 36,348 KB
testcase_100	AC	687 ms 57,996 KB
testcase_101	AC	162 ms 23,288 KB
testcase_102	AC	90 ms 16,424 KB
testcase_103	AC	180 ms 24,116 KB
testcase_104	AC	250 ms 27,432 KB
testcase_105	AC	551 ms 43,700 KB
testcase_106	AC	319 ms 32,556 KB
testcase_107	AC	684 ms 57,152 KB
testcase_108	AC	693 ms 56,572 KB
testcase_109	AC	556 ms 43,492 KB
testcase_110	AC	495 ms 40,776 KB
testcase_111	AC	554 ms 42,556 KB
testcase_112	AC	243 ms 26,768 KB
testcase_113	AC	492 ms 40,120 KB
testcase_114	AC	303 ms 30,788 KB
testcase_115	AC	114 ms 17,724 KB
testcase_116	AC	357 ms 34,396 KB
testcase_117	AC	227 ms 26,912 KB
testcase_118	AC	687 ms 55,048 KB
testcase_119	AC	393 ms 35,996 KB
testcase_120	AC	628 ms 50,900 KB
testcase_121	AC	203 ms 24,992 KB
testcase_122	AC	353 ms 34,196 KB
testcase_123	AC	29 ms 10,880 KB
testcase_124	AC	744 ms 70,792 KB
testcase_125	AC	684 ms 70,788 KB

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

ソースコード

raw source code

import sys
sys.setrecursionlimit(505050)

def bridge(G, N):  # from https://tjkendev.github.io/procon-library/python/graph/bridge.html
    result = set()
    label = [None]*N
    gen = 0
    cost = [0]*N
    def dfs(u, p):
        nonlocal gen
        res = 0
        for v in G[u]:
            if v == p:
                continue
            if label[v] is not None:
                if label[v] < label[u]:
                    cost[v] += 1
                    res += 1
            else:
                label[v] = gen; gen += 1
                r = dfs(v, u)
                if r == 0:
                    result.add((u, v) if u < v else (v, u))
                res += r
        res -= cost[u]
        return res
    for v in range(N):
        if not label[v]:
            label[v] = gen; gen += 1
            r = dfs(v, -1)
            assert r == 0, r
    return result

N = int(input())
G = [[] for _ in range(N)]
d = {}
for i in range(1, N+1):
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
    d[(a, b)] = i

ans = bridge(G, N)
print(N - len(ans))
for a in ans:
    del d[a]
print(" ".join(map(str, d.values())))

yukicoder

結果

テストケース

ソースコード