結果
問題 | No.1190 Points |
ユーザー | H3PO4 |
提出日時 | 2021-12-08 08:54:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 351 ms / 2,000 ms |
コード長 | 1,055 bytes |
コンパイル時間 | 362 ms |
コンパイル使用メモリ | 87,108 KB |
実行使用メモリ | 104,940 KB |
最終ジャッジ日時 | 2023-09-23 00:14:06 |
合計ジャッジ時間 | 11,097 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 91 ms
71,420 KB |
testcase_01 | AC | 90 ms
71,920 KB |
testcase_02 | AC | 89 ms
71,976 KB |
testcase_03 | AC | 263 ms
91,900 KB |
testcase_04 | AC | 224 ms
87,940 KB |
testcase_05 | AC | 222 ms
91,112 KB |
testcase_06 | AC | 272 ms
91,464 KB |
testcase_07 | AC | 293 ms
97,052 KB |
testcase_08 | AC | 290 ms
104,940 KB |
testcase_09 | AC | 292 ms
102,092 KB |
testcase_10 | AC | 294 ms
104,912 KB |
testcase_11 | AC | 250 ms
92,980 KB |
testcase_12 | AC | 300 ms
102,524 KB |
testcase_13 | AC | 253 ms
90,776 KB |
testcase_14 | AC | 134 ms
84,904 KB |
testcase_15 | AC | 329 ms
101,452 KB |
testcase_16 | AC | 141 ms
81,080 KB |
testcase_17 | AC | 314 ms
98,032 KB |
testcase_18 | AC | 201 ms
85,984 KB |
testcase_19 | AC | 130 ms
86,648 KB |
testcase_20 | AC | 239 ms
89,264 KB |
testcase_21 | AC | 162 ms
84,548 KB |
testcase_22 | AC | 149 ms
86,820 KB |
testcase_23 | AC | 351 ms
102,240 KB |
testcase_24 | AC | 317 ms
102,216 KB |
testcase_25 | AC | 279 ms
92,436 KB |
testcase_26 | AC | 188 ms
91,260 KB |
testcase_27 | AC | 269 ms
92,920 KB |
ソースコード
import sys from collections import deque input = sys.stdin.buffer.readline N, M, P = map(int, input().split()) S, G = (int(x) - 1 for x in input().split()) Graph = [[] for _ in range(N)] for _ in range(M): u, v = (int(x) - 1 for x in input().split()) Graph[u].append(v) Graph[v].append(u) INF = 10 ** 9 pair2idx = lambda v, p: v + p * N idx2pair = lambda v2: divmod(v2, N) def dist_parity(v0): dist = [INF] * (2 * N) d = deque([v0]) dist[v0] = 0 while d: v2 = d.popleft() dv = dist[v2] parity, v = idx2pair(v2) for x in Graph[v]: x2 = pair2idx(x, 1 - parity) if dist[x2] == INF: dist[x2] = dv + 1 d.append(x2) return dist dist_s, dist_g = dist_parity(S), dist_parity(G) ans = [] for i in range(N): if dist_s[pair2idx(i, 0)] + dist_g[pair2idx(i, P % 2)] <= P or dist_s[pair2idx(i, 1)] + dist_g[pair2idx(i, 1 - P % 2)] <= P: ans.append(i + 1) if ans: print(len(ans)) print(*ans, sep="\n") else: print(-1)