結果
問題 | No.1477 Lamps on Graph |
ユーザー |
![]() |
提出日時 | 2021-04-16 22:28:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 436 ms / 2,000 ms |
コード長 | 1,801 bytes |
コンパイル時間 | 192 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 111,924 KB |
最終ジャッジ日時 | 2024-07-03 02:33:28 |
合計ジャッジ時間 | 11,144 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
n,m=map(int,input().split())a=[-1]+list(map(int,input().split()))root=[[] for i in range(n+1)]rootr=[[] for i in range(n+1)]import syssys.setrecursionlimit(10**9)for i in range(m):v,u=map(int,input().split())if a[v]>a[u]:root[u].append(v)rootr[v].append(u)elif a[u]>a[v]:root[v].append(u)rootr[u].append(v)memo=[-1]*(n+1)light=[0]*(n+1)ans=[]k=int(input())b=list(map(int,input().split()))for x in b:light[x]=1def ch(x):light[x]^=1ans.append(x)for nod in root[x]:light[nod]^=1seen=[0]*(n+1)ind=[0]*(n+1)def tree_search(n,G,s,func1,func2,func3):#n...頂点の数#G...G[v]は頂点vから行ける頂点の配列#s...sが根#func1(now)...ある頂点に初めて訪れた時、その頂点のみでする処理。ない場合は0#func2(now,next)...nowからnextに移動する時に行う処理。ない場合は0#func3(now)...nowを去る時にする処理。なければ0############## 計算量に注意 場合によっては配列生成をtree_search の外に出してもいい#seen=[0]*(n+1)#ind=[0]*(n+1)# record=[[] for i in range(n+1)] # 変数の情報記録##############search=[s]while search:now=search[-1]if seen[now]==0 and func1!=0:func1(now)if memo[now]==1:passseen[now]=1if len(G[now])>ind[now]:next=G[now][ind[now]]ind[now]+=1if seen[next]>0:continueif func2!=0:func2(now,next)search.append(next)else:if func3!=0:func3(now)search.pop()def f(x):if light[x]==1:ch(x)memo[x]=1for i in range(1,n+1):tree_search(n,rootr,i,0,0,f)print(len(ans))for x in ans:print(x)