結果
問題 | No.1477 Lamps on Graph |
ユーザー |
![]() |
提出日時 | 2023-09-03 20:55:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 248 ms / 2,000 ms |
コード長 | 1,260 bytes |
コンパイル時間 | 468 ms |
コンパイル使用メモリ | 82,036 KB |
実行使用メモリ | 110,192 KB |
最終ジャッジ日時 | 2024-06-13 01:38:17 |
合計ジャッジ時間 | 7,932 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
# ACだがa条件で有向辺を張る、という前回の方針でやってみる# 有向辺にすれば閉路はできない、Ai<Ajだから# すると入次数が0のところからスタートすればいいN, M = map(int, input().split())A = list(map(int, input().split()))edges = [[] for i in range(N)]inward = [0]*Nfor i in range(M):u, v = map(int, input().split())u -= 1v -= 1if A[u] < A[v]:edges[u].append(v)inward[v] += 1elif A[v] < A[u]:edges[v].append(u)inward[u] += 1K = int(input())B = list(map(int, input().split()))switch = [0]*Nfor b in B:switch[b-1] = 1from collections import dequeque = deque()for i in range(N):if inward[i] == 0:que.append(i)ans_list = []while que:current = que.popleft()if switch[current] == 1:ans_list.append(current)for nxt in edges[current]:switch[nxt] ^= 1inward[nxt] -= 1if inward[nxt] == 0:que.append(nxt)elif switch[current] == 0:for nxt in edges[current]:inward[nxt] -= 1if inward[nxt] == 0:que.append(nxt)print(len(ans_list))for a in ans_list:print(a+1)