結果
問題 | No.1477 Lamps on Graph |
ユーザー |
![]() |
提出日時 | 2023-03-10 22:45:42 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 310 ms / 2,000 ms |
コード長 | 1,312 bytes |
コンパイル時間 | 297 ms |
コンパイル使用メモリ | 82,584 KB |
実行使用メモリ | 110,256 KB |
最終ジャッジ日時 | 2024-09-18 04:52:18 |
合計ジャッジ時間 | 11,044 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
# もう一度やる# 入次数0の頂点から調べて、スイッチを押していく# その頂点を調べて、スイッチを押したらnxt頂点のonoffも調整# そうしたらnxt頂点の次数を1つ減らす、次数が0になったら調べるリストに入れるN, M = map(int, input().split())A = [0]+list(map(int, input().split()))edges = [[] for i in range(N+1)]inward = [0]*(N+1)for i in range(M):u, v = map(int, input().split())if A[u] < A[v]:edges[u].append(v)inward[v] += 1elif A[u] > A[v]:edges[v].append(u)inward[u] += 1K = int(input())B = list(map(int, input().split()))on_off = [0]*(N+1)for b in B:on_off[b] = 1from collections import dequeque = deque()for i in range(1, N+1):if inward[i] == 0:que.append(i)ans = []while que:current = que.popleft()if on_off[current] == 0:for nxt in edges[current]:inward[nxt] -= 1if inward[nxt] == 0:que.append(nxt)elif on_off[current] == 1:ans.append(current)for nxt in edges[current]:on_off[nxt] ^= 1inward[nxt] -= 1if inward[nxt] == 0:que.append(nxt)print(len(ans))for a in ans:print(a)