結果
問題 | No.1477 Lamps on Graph |
ユーザー |
![]() |
提出日時 | 2023-03-09 22:05:13 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,647 bytes |
コンパイル時間 | 199 ms |
コンパイル使用メモリ | 82,128 KB |
実行使用メモリ | 116,148 KB |
最終ジャッジ日時 | 2024-09-18 03:04:47 |
合計ジャッジ時間 | 11,899 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 12 WA * 26 |
ソースコード
# 整数の大小関係で有効グラフになる# 各連結成分ごとに調べる、そのために入次数0を記録# 連結成分でON=[0101]を調べる、連結成分の始めから見ていく# switch使ったら記録# BFS or DFSだろう# 問題読み違えていた、ランプは次だけ変わる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()))# その連結成分の始めからやらないと最小手順にならない# ということは連結成分の最初を探す必要がある, degree check# 問題読み違えていた、ランプは次だけ変わるfrom collections import dequeonoff = [0]*(N+1)for b in B:onoff[b] = 1start = []for i in range(1, N+1):if inward[i] == 0:start.append(i)switch_list = []ans = []while start:next_start = []for s in start:if onoff[s] == 1:# スイッチ押すonoff[s] = 0ans.append(s)for nxt in edges[s]:onoff[nxt] ^= 1for nxt in edges[s]:inward[nxt] -= 1# 入次数がゼロになれば、その頂点以前はすべて処理済みということif inward[nxt] == 0:next_start.append(nxt)start = next_startprint(len(ans))for a in ans:print(a)