結果

問題 No.1477 Lamps on Graph
ユーザー kuro_Bkuro_B
提出日時 2023-05-15 22:34:18
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,251 bytes
コンパイル時間 184 ms
コンパイル使用メモリ 82,308 KB
実行使用メモリ 119,184 KB
最終ジャッジ日時 2024-12-14 03:59:05
合計ジャッジ時間 15,139 ms
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 10 WA * 28
権限があれば一括ダウンロードができます

ソースコード

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

######
import sys, re
from copy import copy, deepcopy
from math import ceil, floor, sqrt,factorial, gcd, pi, degrees, radians, sin, asin, cos, acos, tan, atan2
from statistics import mean, median
from collections import Counter, deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations, accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce, lru_cache
from string import ascii_uppercase, ascii_lowercase
from decimal import Decimal, ROUND_HALF_UP #
def input(): return sys.stdin.readline().rstrip('\n')
#easy-testpypy
if __file__=='prog.py':
sys.setrecursionlimit(10**5)
else:
sys.setrecursionlimit(10**6)
def lcm(a, b): return a * b // gcd(a, b)
#3/NMO(NlogM)
def gcd_v2(l: list): return reduce(gcd, l)
def lcm_v2(l: list): return reduce(lcm, l)
#nPk
def nPk(n, k): return factorial(n) // factorial(n - k)
#
def modinv(a, mod=10**9+7): return pow(a, mod-2, mod)
INF = float('inf')
MOD = 10 ** 9 + 7
######
N, M=map(int, input().split())
A=list(map(int, input().split()))
es=[]
for _ in range(M):
a, b = map(int, input().split())
es.append([a,b])
K=int(input())
B=list(map(int, input().split()))
lamps=[0]*N #0off1on
for b in B:
lamps[b-1]=1
graph = [[] for _ in range(N)]
input_edge=[0]*N
for i in range(M):
a,b=es[i]
if A[a-1]<A[b-1]:
graph[a-1].append(b-1)
if lamps[a-1]:
input_edge[b-1]+=1
elif A[a-1]>A[b-1]:
graph[b-1].append(a-1)
if lamps[b-1]:
input_edge[a-1]+=1
ans = [i for i in range(N) if input_edge[i] == 0 and lamps[i]==1]
que=deque(ans)
while que:
q = que.popleft()
lamps[q]=0 #
for e in graph[q]:
input_edge[e] -= 1
lamps[e]=0 if lamps[e]==1 else 1
if input_edge[e] == 0 and lamps[e]==1:
for v in graph[e]:
input_edge[v] += 1
que.append(e)
ans.append(e)
print(len(ans))
for a in ans:
print(a+1)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0