結果
問題 | No.1983 [Cherry 4th Tune C] 南の島のマーメイド |
ユーザー | 👑 Kazun |
提出日時 | 2022-03-29 23:39:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,142 ms / 4,000 ms |
コード長 | 7,488 bytes |
コンパイル時間 | 188 ms |
コンパイル使用メモリ | 82,572 KB |
実行使用メモリ | 250,472 KB |
最終ジャッジ日時 | 2024-04-17 12:33:55 |
合計ジャッジ時間 | 25,612 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 43 ms
56,568 KB |
testcase_01 | AC | 42 ms
55,552 KB |
testcase_02 | AC | 43 ms
56,240 KB |
testcase_03 | AC | 43 ms
55,940 KB |
testcase_04 | AC | 42 ms
57,132 KB |
testcase_05 | AC | 42 ms
55,480 KB |
testcase_06 | AC | 42 ms
56,092 KB |
testcase_07 | AC | 42 ms
56,096 KB |
testcase_08 | AC | 131 ms
79,244 KB |
testcase_09 | AC | 144 ms
80,732 KB |
testcase_10 | AC | 178 ms
81,824 KB |
testcase_11 | AC | 191 ms
82,380 KB |
testcase_12 | AC | 166 ms
81,248 KB |
testcase_13 | AC | 631 ms
141,876 KB |
testcase_14 | AC | 728 ms
146,132 KB |
testcase_15 | AC | 822 ms
177,504 KB |
testcase_16 | AC | 434 ms
141,744 KB |
testcase_17 | AC | 760 ms
145,068 KB |
testcase_18 | AC | 788 ms
176,864 KB |
testcase_19 | AC | 1,048 ms
195,544 KB |
testcase_20 | AC | 734 ms
170,808 KB |
testcase_21 | AC | 794 ms
164,136 KB |
testcase_22 | AC | 877 ms
158,704 KB |
testcase_23 | AC | 1,132 ms
198,992 KB |
testcase_24 | AC | 1,128 ms
198,936 KB |
testcase_25 | AC | 1,099 ms
198,316 KB |
testcase_26 | AC | 1,130 ms
198,976 KB |
testcase_27 | AC | 1,114 ms
200,152 KB |
testcase_28 | AC | 1,142 ms
198,872 KB |
testcase_29 | AC | 1,138 ms
197,216 KB |
testcase_30 | AC | 1,139 ms
198,960 KB |
testcase_31 | AC | 1,107 ms
199,936 KB |
testcase_32 | AC | 1,132 ms
199,640 KB |
testcase_33 | AC | 42 ms
55,116 KB |
testcase_34 | AC | 293 ms
133,052 KB |
testcase_35 | AC | 466 ms
185,456 KB |
testcase_36 | AC | 487 ms
179,748 KB |
testcase_37 | AC | 43 ms
55,476 KB |
testcase_38 | AC | 98 ms
79,396 KB |
testcase_39 | AC | 495 ms
219,212 KB |
testcase_40 | AC | 534 ms
250,472 KB |
ソースコード
class Graph: __slots__=("edge_number", "adjacent") #入力定義 def __init__(self, N=0): """ N 頂点の空グラフ (多重辺なし) を生成する.""" self.edge_number=0 self.adjacent=[set() for _ in range(N)] #頂点の追加 def add_vertex(self): """ 頂点を追加する. """ self.adjacent.append(set()) return self.order()-1 def add_vertices(self, k): """ 頂点を k 個追加する. k: int """ n=self.order() self.adjacent.extend([set() for _ in range(k)]) return list(range(n,n+k)) #辺の追加 def add_edge(self,u,v): """ 無向辺 uv を加える""" if not self.edge_exist(u,v): self.adjacent[u].add(v) self.adjacent[v].add(u) self.edge_number+=1 return self.edge_number-1 else: return -1 #辺を除く def remove_edge(self,u,v): """ 無向辺 uv が存在するならば除く""" if self.edge_exist(u,v): self.adjacent[u].discard(v) self.adjacent[v].discard(u) self.edge_number-=1 return True else: return False def reset_vertex(self, u): """ 頂点 u に接続している辺を全て消す.""" X=self.adjacent[u].copy() for v in X: self.remove_edge(u,v) #Walkの追加 def add_walk(self,*walk): """ walk=(w[0],...,w[n-1]) に対して, n-1 本の辺 w[i]w[i+1] を加える.""" n=len(walk) for i in range(n-1): self.add_edge(walk[i],walk[i+1]) #Cycleの追加 def add_cycle(self,*cycle): """ cycle=(c[0], ..., c[n-1]) を加える. """ self.add_walk(*cycle) self.add_edge(cycle[-1],cycle[0]) #グラフに辺が存在するか否か def edge_exist(self,u,v): """ 辺 uv が存在するか? """ return v in self.adjacent[u] #近傍 def neighbohood(self,v): """ 頂点 v の近傍を求める. """ return self.adjacent[v] #次数 def degree(self,v): """ 頂点 v の次数を求める. """ if v in self.adjacent[v]: return len(self.adjacent[v])+1 else: return len(self.adjacent[v]) #頂点数 def vertex_count(self): """ グラフの頂点数 (位数) を出力する. """ return len(self.adjacent) def order(self): """ グラフの位数 (頂点数) を出力する. """ return len(self.adjacent) #辺数 def edge_count(self): """ 辺の本数 (サイズ) を出力する.""" return self.edge_number def size(self): """ サイズ (辺の本数) を出力する. """ return self.edge_number #頂点vを含む連結成分 def connected_component(self,v): """ 頂点 v を含む連結成分を出力する.""" from collections import deque T=[0]*self.N; T[v]=1 Q=deque([v]) while Q: u=Q.popleft() for w in self.adjacent[u]: if T[w]==0: T[w]=1 Q.append(w) return [x for x in range(self.N) if T[x]] #距離 def distance(self,u,v): """ 2頂点 u,v 間の距離を求める.""" if u==v: return 0 from collections import deque inf=float("inf") T=[inf]*self.N; T[u]=0 Q=deque([u]) while Q: w=Q.popleft() for x in self.adjacent[w]: if T[x]==inf: T[x]=T[w]+1 Q.append(x) if x==v: return T[x] return inf #ある1点からの距離 def distance_all(self,u): """ 頂点 u からの距離を求める.""" from collections import deque inf=float("inf") T=[inf]*self.N; T[u]=0 Q=deque([u]) while Q: w=Q.popleft() for x in self.adjacent[w]: if T[x]==inf: T[x]=T[w]+1 Q.append(x) return T #最短路 def shortest_path(self,u,v): """ u から v への最短路を求める (存在しない場合は None). """ if u==v: return [u] from collections import deque inf=float("inf") T=[-1]*self.N Q=deque([u]); T[u]=u while Q: w=Q.popleft() for x in self.adjacent[w]: if T[x]==-1: T[x]=w Q.append(x) if x==v: P=[v] a=v while a!=u: a=T[a] P.append(a) return P[::-1] return None def edge_yielder(self): g=self.adjacent for v in range(self.vertex_count()): for w in g[v]: if v<w: yield (v,w) def Lowlink(G, mode=0): """ G の ord, lowlink を求める. G: Graph output: (ord, lowlink) """ from collections import deque N=G.vertex_count() ord=[-1]*N; low=[-1]*N flag=[0]*N adj=G.adjacent parent=[-1]*N #BFSパート for v in range(N): if flag[v]: continue k=0 S=deque([v]) T=[] while S: u=S.pop() if flag[u]: continue T.append(u) ord[u]=k k+=1 flag[u]=1 for w in adj[u]: if not flag[w]: S.append(w) parent[w]=u for u in T: low[u]=ord[u] for w in T[:0:-1]: for x in adj[w]: if w==v or x!=parent[w]: low[w]=min(low[w],low[x],ord[x]) if mode==0: return ord, low else: return ord, low, parent #橋列挙 def Bridge(G): """ G にある橋を列挙する. G: Graph """ ord,low=Lowlink(G) return [(u,v) for u,v in G.edge_yielder() if ord[u]<low[v] or ord[v]<low[u]] def Connected_Component_Decomposition(G, mode=0): """ 連結成分毎に分解する. G: Graph mode: 0→連結成分, 1, 連結成分番号, 2→ (連結成分, 連結成分番号)""" from collections import deque N=G.vertex_count() T=[-1]*N C=[] k=0 for v in range(N): if T[v]==-1: Q=deque([v]); T[v]=k c=[] while Q: u=Q.popleft() c.append(u) for w in G.adjacent[u]: if T[w]==-1: T[w]=k Q.append(w) k+=1 C.append(c) if mode==0: return C elif mode==1: return T else: return C,T #================================================== import sys input=sys.stdin.readline write=sys.stdout.write N,M,Q=map(int,input().split()) G=Graph(N+1) for _ in range(M): u,v=map(int,input().split()) G.add_edge(u,v) H=Graph(N+1) for u,v in Bridge(G): H.add_edge(u,v) Id=Connected_Component_Decomposition(H,1) Ans=[""]*Q for q in range(Q): x,y=map(int,input().split()) Ans[q]="Yes" if Id[x]==Id[y] else "No" write("\n".join(Ans))