結果
問題 | No.1477 Lamps on Graph |
ユーザー |
![]() |
提出日時 | 2023-03-09 19:53:13 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,771 bytes |
コンパイル時間 | 176 ms |
コンパイル使用メモリ | 82,700 KB |
実行使用メモリ | 661,316 KB |
最終ジャッジ日時 | 2024-09-18 03:01:57 |
合計ジャッジ時間 | 10,585 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 6 WA * 14 MLE * 1 -- * 17 |
ソースコード
# 整数の大小関係で有効グラフになる# 各連結成分ごとに調べる、そのために入次数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# さらに、1<3, 2<3, 3<4, 3<5のような形だとどこが最初か、いつ確定かが言いにくいfrom collections import dequeonoff = [0]*(N+1)for b in B:onoff[b] = 1ans = [0]*(N+1)for start in range(1, N+1):if inward[start] > 0:continueque = deque()que.append((start, 0)) #2nd for switch countwhile que:current, switch = que.popleft()#print('current', current, 'switch', switch, 'onoff', onoff)if (onoff[current] + switch)%2 == 0:for nxt in edges[current]:#onoff[nxt] += switchque.append((nxt, switch))else:ans[current] += 1for nxt in edges[current]:#onoff[nxt] += switch+1que.append((nxt, switch+1))ans_list = []for i in range(1, N+1):if ans[i] %2 == 1:ans_list.append(i)print(len(ans_list))for a in ans_list:print(a)