結果
問題 | No.1477 Lamps on Graph |
ユーザー |
![]() |
提出日時 | 2023-05-15 22:34:18 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,251 bytes |
コンパイル時間 | 184 ms |
コンパイル使用メモリ | 82,308 KB |
実行使用メモリ | 119,184 KB |
最終ジャッジ日時 | 2024-12-14 03:59:05 |
合計ジャッジ時間 | 15,139 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 10 WA * 28 |
ソースコード
###スニペット始まり###import sys, refrom copy import copy, deepcopyfrom math import ceil, floor, sqrt,factorial, gcd, pi, degrees, radians, sin, asin, cos, acos, tan, atan2from statistics import mean, medianfrom collections import Counter, deque, defaultdictfrom heapq import heapify, heappop, heappushfrom itertools import permutations, accumulate, product, combinations, combinations_with_replacementfrom bisect import bisect, bisect_left, bisect_rightfrom functools import reduce, lru_cachefrom string import ascii_uppercase, ascii_lowercasefrom 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)#nPkdef 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がonfor b in B:lamps[b-1]=1graph = [[] for _ in range(N)]input_edge=[0]*Nfor i in range(M):a,b=es[i]if A[a-1]<A[b-1]:graph[a-1].append(b-1)if lamps[a-1]:input_edge[b-1]+=1elif A[a-1]>A[b-1]:graph[b-1].append(a-1)if lamps[b-1]:input_edge[a-1]+=1ans = [i for i in range(N) if input_edge[i] == 0 and lamps[i]==1]que=deque(ans)while que:q = que.popleft()lamps[q]=0 #消す。for e in graph[q]:input_edge[e] -= 1lamps[e]=0 if lamps[e]==1 else 1if input_edge[e] == 0 and lamps[e]==1:for v in graph[e]:input_edge[v] += 1que.append(e)ans.append(e)print(len(ans))for a in ans:print(a+1)