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

提出ソース

結果

問題	No.1254 補強への架け橋
ユーザー	qib
提出日時	2022-10-17 16:06:20
言語	PyPy3 (7.3.15)
結果	AC
実行時間	283 ms / 2,000 ms
コード長	710 bytes
コンパイル時間	157 ms
コンパイル使用メモリ	81,788 KB
実行使用メモリ	103,920 KB
最終ジャッジ日時	2024-06-28 06:30:39
合計ジャッジ時間	22,943 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	44 ms 54,596 KB
testcase_01	AC	42 ms 53,712 KB
testcase_02	AC	42 ms 53,308 KB
testcase_03	AC	42 ms 54,080 KB
testcase_04	AC	43 ms 54,228 KB
testcase_05	AC	43 ms 53,980 KB
testcase_06	AC	42 ms 54,228 KB
testcase_07	AC	43 ms 54,844 KB
testcase_08	AC	43 ms 53,668 KB
testcase_09	AC	44 ms 54,868 KB
testcase_10	AC	42 ms 54,392 KB
testcase_11	AC	42 ms 54,048 KB
testcase_12	AC	43 ms 53,796 KB
testcase_13	AC	43 ms 54,252 KB
testcase_14	AC	43 ms 54,904 KB
testcase_15	AC	43 ms 54,680 KB
testcase_16	AC	42 ms 55,032 KB
testcase_17	AC	42 ms 54,732 KB
testcase_18	AC	43 ms 53,816 KB
testcase_19	AC	43 ms 55,412 KB
testcase_20	AC	43 ms 54,272 KB
testcase_21	AC	43 ms 54,296 KB
testcase_22	AC	43 ms 55,284 KB
testcase_23	AC	42 ms 54,108 KB
testcase_24	AC	43 ms 54,612 KB
testcase_25	AC	43 ms 54,604 KB
testcase_26	AC	43 ms 55,292 KB
testcase_27	AC	45 ms 54,380 KB
testcase_28	AC	44 ms 54,604 KB
testcase_29	AC	43 ms 54,040 KB
testcase_30	AC	43 ms 54,516 KB
testcase_31	AC	44 ms 54,800 KB
testcase_32	AC	43 ms 54,152 KB
testcase_33	AC	44 ms 54,048 KB
testcase_34	AC	45 ms 54,716 KB
testcase_35	AC	44 ms 54,684 KB
testcase_36	AC	44 ms 54,312 KB
testcase_37	AC	43 ms 55,576 KB
testcase_38	AC	44 ms 54,716 KB
testcase_39	AC	43 ms 54,524 KB
testcase_40	AC	43 ms 55,136 KB
testcase_41	AC	44 ms 54,928 KB
testcase_42	AC	43 ms 54,708 KB
testcase_43	AC	58 ms 64,944 KB
testcase_44	AC	47 ms 56,396 KB
testcase_45	AC	48 ms 57,204 KB
testcase_46	AC	58 ms 64,080 KB
testcase_47	AC	50 ms 56,776 KB
testcase_48	AC	57 ms 64,296 KB
testcase_49	AC	44 ms 54,988 KB
testcase_50	AC	62 ms 67,284 KB
testcase_51	AC	61 ms 66,576 KB
testcase_52	AC	62 ms 65,956 KB
testcase_53	AC	59 ms 64,336 KB
testcase_54	AC	60 ms 65,480 KB
testcase_55	AC	60 ms 66,424 KB
testcase_56	AC	46 ms 55,536 KB
testcase_57	AC	54 ms 62,504 KB
testcase_58	AC	55 ms 63,256 KB
testcase_59	AC	44 ms 55,472 KB
testcase_60	AC	47 ms 55,648 KB
testcase_61	AC	58 ms 64,280 KB
testcase_62	AC	44 ms 54,996 KB
testcase_63	AC	110 ms 77,840 KB
testcase_64	AC	97 ms 77,412 KB
testcase_65	AC	105 ms 77,392 KB
testcase_66	AC	101 ms 77,796 KB
testcase_67	AC	94 ms 76,920 KB
testcase_68	AC	103 ms 77,276 KB
testcase_69	AC	105 ms 77,752 KB
testcase_70	AC	98 ms 77,348 KB
testcase_71	AC	95 ms 77,184 KB
testcase_72	AC	107 ms 77,652 KB
testcase_73	AC	97 ms 77,372 KB
testcase_74	AC	107 ms 77,628 KB
testcase_75	AC	105 ms 77,276 KB
testcase_76	AC	79 ms 74,144 KB
testcase_77	AC	102 ms 77,236 KB
testcase_78	AC	108 ms 77,740 KB
testcase_79	AC	107 ms 77,572 KB
testcase_80	AC	109 ms 77,524 KB
testcase_81	AC	108 ms 77,632 KB
testcase_82	AC	106 ms 78,020 KB
testcase_83	AC	276 ms 93,320 KB
testcase_84	AC	272 ms 92,580 KB
testcase_85	AC	202 ms 89,144 KB
testcase_86	AC	256 ms 91,872 KB
testcase_87	AC	264 ms 93,712 KB
testcase_88	AC	116 ms 77,728 KB
testcase_89	AC	279 ms 93,352 KB
testcase_90	AC	197 ms 88,560 KB
testcase_91	AC	179 ms 86,100 KB
testcase_92	AC	142 ms 81,884 KB
testcase_93	AC	230 ms 89,456 KB
testcase_94	AC	217 ms 88,768 KB
testcase_95	AC	208 ms 88,776 KB
testcase_96	AC	268 ms 93,180 KB
testcase_97	AC	165 ms 83,468 KB
testcase_98	AC	264 ms 93,852 KB
testcase_99	AC	191 ms 87,768 KB
testcase_100	AC	283 ms 93,632 KB
testcase_101	AC	131 ms 81,128 KB
testcase_102	AC	110 ms 77,748 KB
testcase_103	AC	136 ms 81,516 KB
testcase_104	AC	153 ms 82,900 KB
testcase_105	AC	230 ms 89,724 KB
testcase_106	AC	172 ms 83,848 KB
testcase_107	AC	265 ms 93,352 KB
testcase_108	AC	269 ms 93,468 KB
testcase_109	AC	230 ms 89,668 KB
testcase_110	AC	215 ms 88,700 KB
testcase_111	AC	229 ms 89,044 KB
testcase_112	AC	153 ms 82,996 KB
testcase_113	AC	216 ms 88,336 KB
testcase_114	AC	164 ms 83,604 KB
testcase_115	AC	117 ms 78,084 KB
testcase_116	AC	192 ms 85,996 KB
testcase_117	AC	151 ms 82,732 KB
testcase_118	AC	266 ms 93,508 KB
testcase_119	AC	187 ms 87,416 KB
testcase_120	AC	263 ms 93,364 KB
testcase_121	AC	144 ms 82,200 KB
testcase_122	AC	178 ms 86,140 KB
testcase_123	AC	42 ms 53,832 KB
testcase_124	AC	249 ms 103,920 KB
testcase_125	AC	254 ms 103,904 KB

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

ソースコード

raw source code

from collections import deque

n = int(input())

g = [[] for _ in range(n)]
edges = []
for _ in range(n):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  g[a].append(b)
  g[b].append(a)
  edges.append((a, b))

dq = deque()
deg = [len(g[v]) for v in range(n)]
used = [False for _ in range(n)]
for v in range(n):
	if deg[v] == 1:
		deg[v] -= 1
		used[v] = True
		dq.appendleft(v)

while len(dq) > 0:
	cur = dq.pop()
	for nxt in g[cur]:
		if used[nxt]:
			continue
		deg[nxt] -= 1
		if deg[nxt] == 1:
			deg[nxt] -= 1
			used[nxt] = True
			dq.appendleft(nxt)

ans = []
for i in range(len(edges)):
	a, b = edges[i]
	if not used[a] and not used[b]:
	  ans.append(i + 1)

print(len(ans))
print(*ans, sep=" ")

yukicoder

結果

テストケース

ソースコード