結果
問題 | No.1477 Lamps on Graph |
ユーザー |
![]() |
提出日時 | 2023-05-15 22:50:58 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,272 bytes |
コンパイル時間 | 185 ms |
コンパイル使用メモリ | 82,632 KB |
実行使用メモリ | 219,736 KB |
最終ジャッジ日時 | 2024-12-14 04:09:35 |
合計ジャッジ時間 | 18,070 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 9 WA * 28 TLE * 1 |
ソースコード
###スニペット始まり###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 lamps[e]:for v in graph[e]:input_edge[v] += 1if input_edge[e] == 0 and lamps[e]==1:que.append(e)ans.append(e)print(len(ans))for a in ans:print(a+1)