結果
問題 | No.1477 Lamps on Graph |
ユーザー |
![]() |
提出日時 | 2023-01-05 09:04:49 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 313 ms / 2,000 ms |
コード長 | 844 bytes |
コンパイル時間 | 321 ms |
コンパイル使用メモリ | 82,116 KB |
実行使用メモリ | 114,244 KB |
最終ジャッジ日時 | 2024-11-28 22:06:22 |
合計ジャッジ時間 | 12,004 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
N,M=map(int, input().split())A=list(map(int, input().split()))G=[[]for i in range(N)]deg=[0]*Nfor i in range(M):a,b=map(int, input().split())a-=1b-=1if A[a]<A[b]:G[a].append(b)deg[b]+=1if A[a]>A[b]:G[b].append(a)deg[a]+=1V=N# V:頂点数# G[v] = [w, ...]:有向グラフ上の頂点vから到達できる頂点w# deg[v]:頂点vに到達できる頂点の数from collections import dequeans = list(v for v in range(V) if deg[v] == 0)deq = deque(ans)used = [0] * Vwhile deq:v=deq.popleft()for t in G[v]:deg[t]-=1if deg[t]==0:deq.append(t)ans.append(t)L=[0]*NK=int(input())B=list(map(int, input().split()))for b in B:L[b-1]=1F=[]for i in ans:if L[i]==1:F.append(i+1)for nex in G[i]:L[nex]=1-L[nex]print(len(F))for f in F:print(f)