結果

問題 No.1477 Lamps on Graph
ユーザー kuro_Bkuro_B
提出日時 2023-05-15 23:08:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 302 ms / 2,000 ms
コード長 2,320 bytes
コンパイル時間 160 ms
コンパイル使用メモリ 82,444 KB
実行使用メモリ 119,448 KB
最終ジャッジ日時 2024-05-08 04:03:11
合計ジャッジ時間 11,262 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 123 ms
82,540 KB
testcase_01 AC 124 ms
82,516 KB
testcase_02 AC 124 ms
82,644 KB
testcase_03 AC 124 ms
82,508 KB
testcase_04 AC 124 ms
82,532 KB
testcase_05 AC 128 ms
82,580 KB
testcase_06 AC 122 ms
82,564 KB
testcase_07 AC 125 ms
82,436 KB
testcase_08 AC 120 ms
82,520 KB
testcase_09 AC 125 ms
82,316 KB
testcase_10 AC 126 ms
82,492 KB
testcase_11 AC 124 ms
82,652 KB
testcase_12 AC 283 ms
96,304 KB
testcase_13 AC 230 ms
98,700 KB
testcase_14 AC 254 ms
100,752 KB
testcase_15 AC 205 ms
91,184 KB
testcase_16 AC 189 ms
88,156 KB
testcase_17 AC 191 ms
87,456 KB
testcase_18 AC 223 ms
100,568 KB
testcase_19 AC 218 ms
97,084 KB
testcase_20 AC 203 ms
88,656 KB
testcase_21 AC 218 ms
103,004 KB
testcase_22 AC 181 ms
87,336 KB
testcase_23 AC 221 ms
93,524 KB
testcase_24 AC 277 ms
106,796 KB
testcase_25 AC 203 ms
90,152 KB
testcase_26 AC 251 ms
102,572 KB
testcase_27 AC 215 ms
92,608 KB
testcase_28 AC 222 ms
93,468 KB
testcase_29 AC 218 ms
93,192 KB
testcase_30 AC 181 ms
94,872 KB
testcase_31 AC 193 ms
88,516 KB
testcase_32 AC 253 ms
118,652 KB
testcase_33 AC 247 ms
113,700 KB
testcase_34 AC 228 ms
119,448 KB
testcase_35 AC 300 ms
108,336 KB
testcase_36 AC 291 ms
107,508 KB
testcase_37 AC 270 ms
105,988 KB
testcase_38 AC 302 ms
105,952 KB
testcase_39 AC 296 ms
107,524 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

###スニペット始まり###
import sys, re
from copy import copy, deepcopy
from math import ceil, floor, sqrt,factorial, gcd, pi, degrees, radians, sin, asin, cos, acos, tan, atan2
from statistics import mean, median
from collections import Counter, deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations, accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce, lru_cache
from string import ascii_uppercase, ascii_lowercase
from decimal import Decimal, ROUND_HALF_UP #四捨五入用

def input(): return sys.stdin.readline().rstrip('\n')
#easy-testのpypyでは再帰数を下げる。
if __file__=='prog.py':
    sys.setrecursionlimit(10**5)
else:
    sys.setrecursionlimit(10**6)

def lcm(a, b): return a * b // gcd(a, b)

#3つ以上の最大公約数/最小公倍数。Nを要素数、Mを数値の大きさとして、O(NlogM)
def gcd_v2(l: list): return reduce(gcd, l)
def lcm_v2(l: list): return reduce(lcm, l)

#nPk
def nPk(n, k): return factorial(n) // factorial(n - k)

#逆元
def modinv(a, mod=10**9+7): return pow(a, mod-2, mod)
INF = float('inf')
MOD = 10 ** 9 + 7
###スニペット終わり###

N, M=map(int, input().split())
A=list(map(int, input().split()))

es=[]
for _ in range(M):
    a, b = map(int, input().split())
    es.append([a,b])

K=int(input())
B=list(map(int, input().split()))

lamps=[0]*N #0がoff、1がon
for b in B:
    lamps[b-1]=1

graph = [[] for _ in range(N)]
input_edge=[0]*N
for i in range(M):
    a,b=es[i]
    if A[a-1]<A[b-1]:
        graph[a-1].append(b-1)
        input_edge[b-1]+=1
    elif A[a-1]>A[b-1]:
        graph[b-1].append(a-1)  
        input_edge[a-1]+=1

ans = []
que=deque([i for i in range(N) if input_edge[i] == 0])
while que:
    q = que.popleft()
    if not lamps[q]:
        for e in graph[q]:
            input_edge[e] -= 1
            if input_edge[e] == 0:
                que.append(e)
    else:
        #切り替えする。
        lamps[q]=0 #消す。
        ans.append(q)
        for e in graph[q]:
            input_edge[e] -= 1
            lamps[e]=0 if lamps[e]==1 else 1
            if input_edge[e] == 0:
                que.append(e)
                
print(len(ans))
for a in ans:
    print(a+1)
0