結果
問題 | No.1477 Lamps on Graph |
ユーザー | 👑 Kazun |
提出日時 | 2021-04-16 21:22:31 |
言語 | PyPy3 (7.3.13) |
結果 |
AC
|
実行時間 | 584 ms / 2,000 ms |
コード長 | 5,549 bytes |
コンパイル時間 | 283 ms |
コンパイル使用メモリ | 87,352 KB |
実行使用メモリ | 172,428 KB |
最終ジャッジ日時 | 2023-09-15 23:23:14 |
合計ジャッジ時間 | 14,348 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 92 ms
71,824 KB |
testcase_01 | AC | 92 ms
71,788 KB |
testcase_02 | AC | 89 ms
71,780 KB |
testcase_03 | AC | 91 ms
71,724 KB |
testcase_04 | AC | 89 ms
71,516 KB |
testcase_05 | AC | 90 ms
71,824 KB |
testcase_06 | AC | 90 ms
71,736 KB |
testcase_07 | AC | 91 ms
71,956 KB |
testcase_08 | AC | 90 ms
71,844 KB |
testcase_09 | AC | 91 ms
71,948 KB |
testcase_10 | AC | 91 ms
71,852 KB |
testcase_11 | AC | 90 ms
71,720 KB |
testcase_12 | AC | 404 ms
117,336 KB |
testcase_13 | AC | 371 ms
117,124 KB |
testcase_14 | AC | 452 ms
120,720 KB |
testcase_15 | AC | 270 ms
91,708 KB |
testcase_16 | AC | 232 ms
97,936 KB |
testcase_17 | AC | 226 ms
97,524 KB |
testcase_18 | AC | 315 ms
138,464 KB |
testcase_19 | AC | 359 ms
119,812 KB |
testcase_20 | AC | 245 ms
87,876 KB |
testcase_21 | AC | 299 ms
130,596 KB |
testcase_22 | AC | 189 ms
82,696 KB |
testcase_23 | AC | 306 ms
94,008 KB |
testcase_24 | AC | 489 ms
133,660 KB |
testcase_25 | AC | 265 ms
90,032 KB |
testcase_26 | AC | 447 ms
132,088 KB |
testcase_27 | AC | 331 ms
97,376 KB |
testcase_28 | AC | 345 ms
114,140 KB |
testcase_29 | AC | 314 ms
100,204 KB |
testcase_30 | AC | 206 ms
111,036 KB |
testcase_31 | AC | 224 ms
100,612 KB |
testcase_32 | AC | 371 ms
170,436 KB |
testcase_33 | AC | 375 ms
172,428 KB |
testcase_34 | AC | 253 ms
145,152 KB |
testcase_35 | AC | 583 ms
156,740 KB |
testcase_36 | AC | 578 ms
154,076 KB |
testcase_37 | AC | 572 ms
147,796 KB |
testcase_38 | AC | 584 ms
149,480 KB |
testcase_39 | AC | 576 ms
154,004 KB |
ソースコード
class Digraph: """重み[なし]有向グラフを生成する. """ #入力定義 def __init__(self,vertex=[]): self.vertex=set(vertex) self.edge_number=0 self.vertex_number=len(vertex) self.adjacent_out={v:set() for v in vertex} #出近傍(vが始点) self.adjacent_in={v:set() for v in vertex} #入近傍(vが終点) #頂点の追加 def add_vertex(self,*adder): for v in adder: if not self.vertex_exist(v): self.adjacent_in[v]=set() self.adjacent_out[v]=set() self.vertex.add(v) self.vertex_number+=1 #辺の追加 def add_edge(self,From,To): self.add_vertex(From) self.add_vertex(To) if To not in self.adjacent_out[From]: self.adjacent_out[From].add(To) self.adjacent_in[To].add(From) self.edge_number+=1 #辺を除く def remove_edge(self,From,To): self.add_vertex(From) self.add_vertex(To) if To in self.adjacent_out[From]: self.adjacent_out[From].discard(To) self.adjacent_in[To].discard(From) self.edge_number-=1 #頂点を除く def remove_vertex(self,*vertexes): for v in vertexes: if v in self.vertex: self.vertex_number-=1 for u in self.adjacent_out[v]: self.adjacent_in[u].discard(v) self.edge_number-=1 del self.adjacent_out[v] for u in self.adjacent_in[v]: self.adjacent_out[u].discard(v) self.edge_number-=1 del self.adjacent_in[v] self.vertex.discard(v) #Walkの追加 def add_walk(self,*walk): N=len(walk) for k in range(N-1): self.add_edge(walk[k],walk[k+1]) #Cycleの追加 def add_cycle(self,*cycle): self.add_walk(*cycle) self.add_edge(cycle[-1],cycle[0]) #頂点の交換 def __vertex_swap(self,p,q): self.vertex.sort() #グラフに頂点が存在するか否か def vertex_exist(self,v): return v in self.vertex #グラフに辺が存在するか否か def edge_exist(self,From,To): if self.vertex_exist(From) and self.vertex_exist(To): return False return To in self.adjacent_out[From] #近傍 def neighbohood(self,v): """vの出近傍, 入近傍を出力する. Input: v:頂点 Output: (出近傍, 入近傍) """ if not self.vertex_exist(v): return (set(),set()) return (self.adjacent_out[v],self.adjacent_in[v]) #出次数 def out_degree(self,v): if not self.vertex_exist(v): return 0 return len(self.adjacent_out[v]) #入次数 def in_degree(self,v): if not self.vertex_exist(v): return 0 return len(self.adjacent_in[v]) #次数 def degree(self,v): return (self.out_degree(v),self.in_degree(v)) #頂点数 def vertex_count(self): return self.vertex_number #辺数 def edge_count(self): return self.edge_number #頂点vに到達可能な頂点 def reachable_to(self,v): if not self.vertex_exist(v): return [] from collections import deque T={v:0 for v in self.vertex} T[v]=1 Q=deque([v]) while Q: x=Q.popleft() for y in self.adjacent_in[x]: if not T[y]: T[y]=1 Q.append(y) return [x for x in self.vertex if T[x]] #頂点vから到達可能な頂点 def reachable_from(self,v): if not self.vertex_exist(v): return [] from collections import deque T={v:0 for v in self.vertex} T[v]=1 Q=deque([v]) while Q: x=Q.popleft() for y in self.adjacent_out[x]: if not T[y]: T[y]=1 Q.append(y) return [x for x in self.vertex if T[x]] #深いコピー def deepcopy(self): from copy import deepcopy D=Digraph() D.vertex=deepcopy(self.vertex) D.edge_number=self.edge_number D.vertex_number=len(self.vertex) D.adjacent_out=deepcopy(self.adjacent_out) D.adjacent_in=deepcopy(self.adjacent_in) return D #Topologycal Sort def Topological_Sort(D): from collections import deque X={v:D.in_degree(v) for v in D.vertex} Q=deque([v for v in D.vertex if X[v]==0]) S=[] while Q: u=Q.pop() S.append(u) for v in D.adjacent_out[u]: X[v]-=1 if X[v]==0: Q.append(v) return S #================================================ import sys from collections import deque input=sys.stdin.readline write=sys.stdout.write N,M=map(int,input().split()) A=["*"]+list(map(int,input().split())) D=Digraph(list(range(1,N+1))) for _ in range(M): u,v=map(int,input().split()) if A[u]<A[v]: D.add_edge(u,v) elif A[u]>A[v]: D.add_edge(v,u) K=int(input()) B=list(map(int,input().split())) Lamp=[0]*(N+1) for b in B: Lamp[b]=1 T=Topological_Sort(D) Z=[] for x in T: if Lamp[x]==1: Z.append(x) for y in D.adjacent_out[x]: Lamp[y]^=1 print(len(Z)) write("\n".join(map(str,Z)))