結果
問題 | No.1477 Lamps on Graph |
ユーザー |
|
提出日時 | 2024-11-04 12:29:26 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 354 ms / 2,000 ms |
コード長 | 895 bytes |
コンパイル時間 | 443 ms |
コンパイル使用メモリ | 82,516 KB |
実行使用メモリ | 110,076 KB |
最終ジャッジ日時 | 2024-11-04 12:29:38 |
合計ジャッジ時間 | 12,311 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
from collections import dequeN,M = map(int,input().split())A = [0]+list(map(int,input().split()))G = {i:[] for i in range(1,N+1)}indeg = [0]*(N+1)for _ in range(M):u,v = map(int,input().split())if A[u]>A[v]:G[v].append(u)indeg[u] += 1if A[u]<A[v]:G[u].append(v)indeg[v] += 1K = int(input())B = list(map(int,input().split()))L = [0]*(N+1)for i in range(K):L[B[i]] = 1que = deque([])for i in range(1,N+1):if indeg[i]==0:que.append(i)ans = []while que:x = que.popleft()if L[x]==1:flag = 1else:flag = 0if flag==1:ans.append(x)L[x] = 0for y in G[x]:indeg[y] -= 1if flag==1:L[y] = 1-L[y]if indeg[y]==0:que.append(y)if sum(L)==0:print(len(ans))for a in ans:print(a)else:print(-1)