結果
問題 | No.1477 Lamps on Graph |
ユーザー |
![]() |
提出日時 | 2021-04-16 20:33:45 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 252 ms / 2,000 ms |
コード長 | 1,111 bytes |
コンパイル時間 | 192 ms |
コンパイル使用メモリ | 82,384 KB |
実行使用メモリ | 110,196 KB |
最終ジャッジ日時 | 2024-07-02 22:56:23 |
合計ジャッジ時間 | 7,974 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
import sysfrom collections import dequeinput = sys.stdin.buffer.readlinen, m = map(int, input().split())A = list(map(int, input().split()))graph = [[] for _ in range(n)]deg = [0] * nfor _ in range(m):a, b = map(int, input().split())a, b = a - 1, b - 1if A[b] > A[a]:graph[a].append(b)deg[b] += 1if A[a] > A[b]:graph[b].append(a)deg[a] += 1k = int(input())B = list(map(int, input().split()))finished = [0] * nlamp = [0] * nfor b in B:lamp[b - 1] = 1start = deque()for i in range(n):if deg[i] == 0:start.append(i)ans = []while start:v = start.popleft()finished[v] = 1if lamp[v] == 0:for u in graph[v]:deg[u] -= 1if deg[u] == 0:start.append(u)else:ans.append(v + 1)lamp[v] = 0finished[v] = 1for u in graph[v]:lamp[u] ^= 1deg[u] -= 1if deg[u] == 0:start.append(u)if sum(lamp) > 0:print(-1)exit()print(len(ans))for a in ans:print(a)