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

提出ソース

結果

問題	No.1254 補強への架け橋
ユーザー	brthyyjp
提出日時	2020-10-09 23:02:46
言語	PyPy3 (7.3.15)
結果	AC
実行時間	332 ms / 2,000 ms
コード長	1,743 bytes
コンパイル時間	308 ms
コンパイル使用メモリ	81,584 KB
実行使用メモリ	133,696 KB
最終ジャッジ日時	2024-07-20 13:51:20
合計ジャッジ時間	22,991 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	37 ms 52,352 KB
testcase_01	AC	37 ms 52,224 KB
testcase_02	AC	37 ms 52,480 KB
testcase_03	AC	37 ms 52,096 KB
testcase_04	AC	37 ms 52,224 KB
testcase_05	AC	38 ms 52,608 KB
testcase_06	AC	38 ms 52,224 KB
testcase_07	AC	39 ms 52,608 KB
testcase_08	AC	38 ms 52,352 KB
testcase_09	AC	37 ms 52,480 KB
testcase_10	AC	37 ms 52,352 KB
testcase_11	AC	38 ms 52,196 KB
testcase_12	AC	38 ms 51,968 KB
testcase_13	AC	38 ms 52,736 KB
testcase_14	AC	42 ms 52,608 KB
testcase_15	AC	38 ms 52,608 KB
testcase_16	AC	40 ms 52,480 KB
testcase_17	AC	38 ms 52,096 KB
testcase_18	AC	39 ms 52,736 KB
testcase_19	AC	39 ms 52,480 KB
testcase_20	AC	39 ms 52,992 KB
testcase_21	AC	39 ms 52,096 KB
testcase_22	AC	40 ms 52,352 KB
testcase_23	AC	38 ms 52,224 KB
testcase_24	AC	38 ms 52,864 KB
testcase_25	AC	39 ms 52,736 KB
testcase_26	AC	39 ms 52,736 KB
testcase_27	AC	39 ms 52,864 KB
testcase_28	AC	40 ms 52,608 KB
testcase_29	AC	38 ms 52,224 KB
testcase_30	AC	38 ms 52,608 KB
testcase_31	AC	39 ms 52,480 KB
testcase_32	AC	37 ms 52,224 KB
testcase_33	AC	38 ms 52,736 KB
testcase_34	AC	38 ms 52,608 KB
testcase_35	AC	37 ms 52,736 KB
testcase_36	AC	38 ms 52,608 KB
testcase_37	AC	40 ms 52,864 KB
testcase_38	AC	39 ms 52,608 KB
testcase_39	AC	37 ms 52,352 KB
testcase_40	AC	38 ms 52,736 KB
testcase_41	AC	38 ms 52,864 KB
testcase_42	AC	37 ms 52,864 KB
testcase_43	AC	50 ms 61,824 KB
testcase_44	AC	39 ms 53,632 KB
testcase_45	AC	41 ms 53,120 KB
testcase_46	AC	48 ms 60,800 KB
testcase_47	AC	42 ms 54,272 KB
testcase_48	AC	48 ms 60,416 KB
testcase_49	AC	38 ms 52,736 KB
testcase_50	AC	51 ms 62,976 KB
testcase_51	AC	49 ms 62,592 KB
testcase_52	AC	51 ms 62,336 KB
testcase_53	AC	49 ms 61,440 KB
testcase_54	AC	51 ms 62,080 KB
testcase_55	AC	51 ms 61,824 KB
testcase_56	AC	39 ms 52,992 KB
testcase_57	AC	46 ms 59,520 KB
testcase_58	AC	47 ms 60,928 KB
testcase_59	AC	39 ms 52,608 KB
testcase_60	AC	41 ms 53,632 KB
testcase_61	AC	49 ms 61,696 KB
testcase_62	AC	40 ms 52,864 KB
testcase_63	AC	120 ms 79,360 KB
testcase_64	AC	90 ms 77,336 KB
testcase_65	AC	109 ms 78,604 KB
testcase_66	AC	101 ms 77,636 KB
testcase_67	AC	85 ms 76,928 KB
testcase_68	AC	105 ms 78,120 KB
testcase_69	AC	114 ms 78,468 KB
testcase_70	AC	97 ms 77,392 KB
testcase_71	AC	90 ms 77,056 KB
testcase_72	AC	112 ms 78,644 KB
testcase_73	AC	95 ms 77,292 KB
testcase_74	AC	116 ms 78,932 KB
testcase_75	AC	105 ms 77,540 KB
testcase_76	AC	69 ms 71,040 KB
testcase_77	AC	99 ms 78,056 KB
testcase_78	AC	116 ms 79,288 KB
testcase_79	AC	116 ms 79,232 KB
testcase_80	AC	110 ms 78,864 KB
testcase_81	AC	120 ms 79,260 KB
testcase_82	AC	111 ms 79,132 KB
testcase_83	AC	327 ms 133,696 KB
testcase_84	AC	326 ms 125,988 KB
testcase_85	AC	232 ms 109,808 KB
testcase_86	AC	281 ms 117,808 KB
testcase_87	AC	302 ms 123,996 KB
testcase_88	AC	122 ms 81,228 KB
testcase_89	AC	317 ms 126,516 KB
testcase_90	AC	229 ms 107,684 KB
testcase_91	AC	203 ms 102,060 KB
testcase_92	AC	149 ms 89,212 KB
testcase_93	AC	279 ms 115,936 KB
testcase_94	AC	256 ms 111,876 KB
testcase_95	AC	257 ms 111,628 KB
testcase_96	AC	299 ms 124,960 KB
testcase_97	AC	190 ms 97,120 KB
testcase_98	AC	296 ms 125,012 KB
testcase_99	AC	217 ms 107,764 KB
testcase_100	AC	332 ms 132,620 KB
testcase_101	AC	142 ms 87,328 KB
testcase_102	AC	119 ms 80,940 KB
testcase_103	AC	149 ms 89,196 KB
testcase_104	AC	166 ms 92,432 KB
testcase_105	AC	267 ms 117,624 KB
testcase_106	AC	190 ms 99,688 KB
testcase_107	AC	332 ms 128,768 KB
testcase_108	AC	314 ms 128,392 KB
testcase_109	AC	273 ms 117,000 KB
testcase_110	AC	250 ms 111,712 KB
testcase_111	AC	248 ms 113,376 KB
testcase_112	AC	162 ms 92,108 KB
testcase_113	AC	256 ms 111,092 KB
testcase_114	AC	184 ms 97,344 KB
testcase_115	AC	122 ms 81,408 KB
testcase_116	AC	203 ms 102,544 KB
testcase_117	AC	168 ms 92,100 KB
testcase_118	AC	299 ms 124,668 KB
testcase_119	AC	211 ms 101,508 KB
testcase_120	AC	308 ms 123,932 KB
testcase_121	AC	154 ms 89,048 KB
testcase_122	AC	213 ms 101,664 KB
testcase_123	AC	38 ms 51,968 KB
testcase_124	AC	305 ms 121,592 KB
testcase_125	AC	308 ms 121,464 KB

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

ソースコード

raw source code

def lowlink(g, root=0):
    n = len(g)
    order = [n]*n
    low = [n]*n

    s = [root]
    cnt = 0
    par = [-1]*n
    seq = []
    while s:
        v = s.pop()
        if order[v] != n:
            continue
        order[v] = cnt
        seq.append(v)
        low[v] = cnt
        cnt += 1
        for u in g[v]:
            if order[u] < cnt:
                if par[v] != u:
                    low[v] = min(low[v], order[u])
                    continue
            else:
                par[u] = v
                s.append(u)
    child = [[] for _ in range(n)]
    for v in range(n):
        if par[v] != -1:
            child[par[v]].append(v)
    seq.reverse()
    for v in seq:
        for u in child[v]:
            low[v] = min(low[v], low[u])
    # bridge
    bridge = []
    for p in range(n):
        for c in child[p]:
            if order[p] < low[c]:
                bridge.append((p, c))

    # articulation points
    AP = []
    for v in range(n):
        if v == root:
            if len(child[v]) >= 2:
                AP.append(v)
        else:
            for c in child[v]:
                if order[v] <= low[c]:
                    AP.append(v)
                    break
    return AP, bridge

import sys
import io, os
input = sys.stdin.buffer.readline

n = int(input())
g = [[] for _ in range(n)]
d = {}
for i in range(n):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    if a > b:
        a, b = b, a
    g[a].append(b)
    g[b].append(a)
    d[(a, b)] = i
#print(d)
_, bridge = lowlink(g, 0)
s = set()
for u, v in bridge:
    if u > v:
        u, v = v, u
    s.add((u, v))

res = []
for k, v in d.items():
    if k in s:
        continue
    else:
        res.append(v+1)
print(len(res))
print(*res)

yukicoder

結果

テストケース

ソースコード