結果

問題 No.1477 Lamps on Graph
ユーザー taiga000629
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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 sys
sys.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]=1
def ch(x):
light[x]^=1
ans.append(x)
for nod in root[x]:
light[nod]^=1
seen=[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)...nownext0
#func3(now)...now0
############## 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:pass
seen[now]=1
if len(G[now])>ind[now]:
next=G[now][ind[now]]
ind[now]+=1
if seen[next]>0:continue
if 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]=1
for i in range(1,n+1):tree_search(n,rootr,i,0,0,f)
print(len(ans))
for x in ans:print(x)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0