結果
問題 | No.1190 Points |
ユーザー | McGregorsh |
提出日時 | 2023-07-13 23:39:35 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,484 bytes |
コンパイル時間 | 291 ms |
コンパイル使用メモリ | 86,780 KB |
実行使用メモリ | 134,688 KB |
最終ジャッジ日時 | 2023-10-13 12:16:50 |
合計ジャッジ時間 | 17,246 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 230 ms
89,912 KB |
testcase_01 | AC | 231 ms
89,964 KB |
testcase_02 | AC | 233 ms
89,784 KB |
testcase_03 | AC | 516 ms
116,764 KB |
testcase_04 | AC | 438 ms
110,480 KB |
testcase_05 | WA | - |
testcase_06 | AC | 507 ms
118,828 KB |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | AC | 517 ms
129,392 KB |
testcase_10 | AC | 500 ms
133,544 KB |
testcase_11 | WA | - |
testcase_12 | AC | 514 ms
130,244 KB |
testcase_13 | AC | 458 ms
115,248 KB |
testcase_14 | AC | 284 ms
103,048 KB |
testcase_15 | AC | 605 ms
129,668 KB |
testcase_16 | AC | 285 ms
96,392 KB |
testcase_17 | AC | 626 ms
126,956 KB |
testcase_18 | AC | 385 ms
104,728 KB |
testcase_19 | AC | 284 ms
106,444 KB |
testcase_20 | AC | 433 ms
110,752 KB |
testcase_21 | WA | - |
testcase_22 | AC | 333 ms
111,944 KB |
testcase_23 | AC | 630 ms
131,028 KB |
testcase_24 | AC | 606 ms
130,488 KB |
testcase_25 | AC | 512 ms
119,624 KB |
testcase_26 | AC | 407 ms
117,096 KB |
testcase_27 | AC | 515 ms
119,608 KB |
ソースコード
import sys from sys import stdin from fractions import Fraction import math from math import ceil, floor, sqrt, pi, factorial, gcd from copy import deepcopy from collections import Counter, deque, defaultdict from heapq import heapify, heappop, heappush from itertools import accumulate, product, combinations, combinations_with_replacement, permutations from bisect import bisect, bisect_left, bisect_right from functools import reduce, lru_cache from decimal import Decimal, getcontext, ROUND_HALF_UP def i_input(): return int(stdin.readline()) def i_map(): return map(int, stdin.readline().split()) def i_list(): return list(i_map()) def s_input(): return stdin.readline()[:-1] def s_map(): return s_input().split() def s_list(): return list(s_map()) def lcm(a, b): return a * b // gcd(a, b) def get_distance(x1, y1, x2, y2): d = sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2) return d def rotate(table): n_fild = [] for x in zip(*table[::-1]): n_fild.append(x) return n_fild sys.setrecursionlimit(10 ** 7) INF = float('inf') MOD = 10 ** 9 + 7 MOD2 = 998244353 alpa = 'abcdefghijklmnopqrstuvwxyz' ALPA = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' def main(): N, M, P = i_map() S, G = i_map() S -= 1 G -= 1 nums = [[] for i in range(N*2)] for i in range(M): a, b = i_map() a -= 1 b -= 1 nums[a].append(N+b) nums[b].append(N+a) nums[N+a].append(b) nums[N+b].append(a) Sscore = [INF] * (N*2) Sscore[S] = 0 que = deque() que.append(S) while que: p = que.popleft() for nxt in nums[p]: if Sscore[nxt] == INF: Sscore[nxt] = Sscore[p] + 1 que.append(nxt) Gscore = [INF] * (N*2) Gscore[G] = 0 gque = deque() gque.append(G) while gque: p = gque.popleft() for nxt in nums[p]: if Gscore[nxt] == INF: Gscore[nxt] = Gscore[p] + 1 gque.append(nxt) ans = set() for i in range(N): a = Sscore[i] b = Sscore[i+N] c = Gscore[i] d = Gscore[i+N] if P % 2 == 0: if (a+c) <= P: ans.add(i+1) if (b+a) <= P: ans.add(i+1) else: if (a+d)<= P: ans.add(i+1) if (b+c) <= P: ans.add(i+1) ans = list(ans) if len(ans) == 0: print(-1) exit() print(len(ans)) ans.sort() for i in ans: print(i) if __name__ == '__main__': main()