結果
問題 | No.1477 Lamps on Graph |
ユーザー | McGregorsh |
提出日時 | 2022-07-19 21:58:48 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 761 ms / 2,000 ms |
コード長 | 2,103 bytes |
コンパイル時間 | 271 ms |
コンパイル使用メモリ | 86,868 KB |
実行使用メモリ | 138,780 KB |
最終ジャッジ日時 | 2023-09-14 18:51:55 |
合計ジャッジ時間 | 23,074 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 241 ms
92,488 KB |
testcase_01 | AC | 244 ms
92,316 KB |
testcase_02 | AC | 245 ms
92,224 KB |
testcase_03 | AC | 248 ms
92,424 KB |
testcase_04 | AC | 239 ms
92,392 KB |
testcase_05 | AC | 242 ms
92,492 KB |
testcase_06 | AC | 242 ms
92,508 KB |
testcase_07 | AC | 240 ms
92,416 KB |
testcase_08 | AC | 239 ms
92,384 KB |
testcase_09 | AC | 240 ms
92,396 KB |
testcase_10 | AC | 240 ms
92,212 KB |
testcase_11 | AC | 240 ms
92,508 KB |
testcase_12 | AC | 508 ms
106,948 KB |
testcase_13 | AC | 492 ms
110,480 KB |
testcase_14 | AC | 550 ms
109,100 KB |
testcase_15 | AC | 378 ms
98,660 KB |
testcase_16 | AC | 393 ms
101,872 KB |
testcase_17 | AC | 391 ms
101,760 KB |
testcase_18 | AC | 624 ms
124,424 KB |
testcase_19 | AC | 513 ms
111,196 KB |
testcase_20 | AC | 358 ms
97,760 KB |
testcase_21 | AC | 557 ms
116,988 KB |
testcase_22 | AC | 319 ms
96,568 KB |
testcase_23 | AC | 405 ms
101,420 KB |
testcase_24 | AC | 605 ms
117,496 KB |
testcase_25 | AC | 362 ms
98,616 KB |
testcase_26 | AC | 633 ms
119,704 KB |
testcase_27 | AC | 404 ms
101,232 KB |
testcase_28 | AC | 463 ms
106,100 KB |
testcase_29 | AC | 432 ms
102,464 KB |
testcase_30 | AC | 419 ms
108,936 KB |
testcase_31 | AC | 402 ms
103,408 KB |
testcase_32 | AC | 725 ms
138,672 KB |
testcase_33 | AC | 699 ms
136,036 KB |
testcase_34 | AC | 432 ms
138,780 KB |
testcase_35 | AC | 761 ms
129,016 KB |
testcase_36 | AC | 761 ms
125,860 KB |
testcase_37 | AC | 699 ms
118,008 KB |
testcase_38 | AC | 746 ms
120,840 KB |
testcase_39 | AC | 751 ms
126,880 KB |
ソースコード
import sys, re from fractions import Fraction 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 from decimal import Decimal, getcontext def i_input(): return int(input()) def i_map(): return map(int, input().split()) def i_list(): return list(i_map()) def i_row(N): return [i_input() for _ in range(N)] def i_row_list(N): return [i_list() for _ in range(N)] def s_input(): return input() def s_map(): return input().split() def s_list(): return list(s_map()) def s_row(N): return [s_input for _ in range(N)] def s_row_str(N): return [s_list() for _ in range(N)] def s_row_list(N): return [list(s_input()) for _ in range(N)] 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 ###関数コピーしたか?### def main(): n, m = i_map() A = i_list() lines = [] for i in range(n): lines.append([A[i], i]) lines.sort() nums = [[] for i in range(n)] for i in range(m): a, b = i_map() a -= 1 b -= 1 nums[a].append(b) nums[b].append(a) k = int(input()) B = i_list() juge = [False] * n for i in range(k): juge[B[i]-1] = True cou = [] for i in range(n): score, num = lines[i] if juge[num]: juge[num] = False cou.append(num+1) for j in nums[num]: if A[num] < A[j]: juge[j] = not juge[j] if len(cou) != 0: print(len(cou)) for i in cou: print(i) else: print(-1) if __name__ == '__main__': main()