結果
| 問題 |
No.1983 [Cherry 4th Tune C] 南の島のマーメイド
|
| コンテスト | |
| ユーザー |
👑  Kazun
|
| 提出日時 | 2024-02-12 11:24:29 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,457 ms / 4,000 ms |
| コード長 | 9,712 bytes |
| コンパイル時間 | 265 ms |
| コンパイル使用メモリ | 82,448 KB |
| 実行使用メモリ | 262,736 KB |
| 最終ジャッジ日時 | 2024-09-28 17:55:26 |
| 合計ジャッジ時間 | 31,670 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 41 |
ソースコード
class Graph:
__slots__=("edge_offset", "edge_alive", "edge_ids", "vertex_alive", "adjacent", "deg")
#入力定義
def __init__(self, N = 0, edge_offset = 0):
""" N 頂点の空グラフ (多重辺なし) を生成する."""
self.adjacent = [[] for _ in range(N)]
self.edge_ids = [[] for _ in range(N)]
self.vertex_alive = [1] * N
self.edge_offset = edge_offset
self.edge_alive = [0] * edge_offset
self.deg = [0] * N
#頂点の追加
def add_vertex(self):
""" 頂点を追加する.
"""
self.adjacent.append([])
self.edge_ids.append([])
self.vertex_alive.append(1)
self.deg.append(0)
return self.order() - 1
def add_vertices(self, k):
""" 頂点を k 個追加する.
k: int
"""
n=self.order()
self.adjacent.extend([[] for _ in range(k)])
self.edge_ids.extend([[] for _ in range(k)])
self.vertex_alive.extend([1] * k)
self.deg.extend([0] * k)
return list(range(n, n + k))
#辺の追加
def add_edge(self, u, v):
""" 無向辺 uv を加える"""
j = len(self.edge_alive)
self.adjacent[u].append(v)
self.adjacent[v].append(u)
self.edge_ids[u].append(j)
self.edge_ids[v].append(j)
self.deg[u] += 1; self.deg[v] += 1
self.edge_alive.append(1)
return j
#辺を除く
def remove_edge(self,u,v):
""" 無向辺 uv が存在するならば除く"""
pass
def reset_vertex(self, u):
""" 頂点 u に接続している辺を全て消す."""
pass
#Walkの追加
def add_walk(self, *walk):
""" walk=(w[0],...,w[n-1]) に対して, n-1 本の辺 w[i]w[i+1] を加える."""
for i in range(len(walk) - 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 が存在するか? """
pass
def partner(self, v):
adj = self.adjacent[v]
edge_ids = self.edge_ids[v]
return [adj[k] for k in range(len(edge_ids)) if self.edge_alive[edge_ids[k]]]
def partner_with_index(self, v):
adj = self.adjacent[v]
edge_ids = self.edge_ids[v]
return [(adj[k], edge_ids[k]) for k in range(len(edge_ids)) if self.edge_alive[edge_ids[k]]]
#近傍
def neighborhood(self, v):
""" 頂点 v の近傍を求める. """
adj = self.adjacent[v]
edge_ids = self.edge_ids[v]
return list(set(adj[k] for k in range(len(edge_ids)) if self.edge_alive[edge_ids[k]]))
#次数
def degree(self, v):
""" 頂点 v の次数を求める. """
return self.deg[v]
#頂点数
def vertex_count(self):
""" グラフの頂点数 (位数) を出力する. """
return len(self.adjacent)
def order(self):
""" グラフの位数 (頂点数) を出力する. """
return len(self.adjacent)
#辺数
def edge_count(self):
""" 辺の本数 (サイズ) を出力する."""
return len(self.edge_alive) - self.edge_offset
def size(self):
""" サイズ (辺の本数) を出力する. """
return len(self.edge_alive) - self.edge_offset
#頂点vを含む連結成分
def connected_component(self, v):
""" 頂点 v を含む連結成分を出力する."""
N = self.order()
stack = [v]
comp = [0] * N; comp[v] = 1
while stack:
x = stack.pop()
for y in self.neighborhood(x):
if comp[y] == 0:
comp[y] = 1
stack.append(y)
return [x for x in range(N) if comp[x]]
#距離
def distance(self, u, v, default):
""" 2頂点 u,v 間の距離を求める."""
if u == v:
return 0
from collections import deque
N = self.order()
dist = [-1] * N; dist[u]=0
queue = deque([u])
while queue:
x = queue.popleft()
for y in self.neighborhood(x):
if dist[y] == -1:
dist[y] = dist[x] + 1
queue.append(y)
if y == v:
return dist[v]
return default
#ある1点からの距離
def distance_all(self,u,default=-1):
""" 頂点 u からの距離を求める."""
from collections import deque
N = self.order()
dist = [-1] * N; dist[u]=0
queue = deque([u])
while queue:
x = queue.popleft()
for y in self.neighborhood(x):
if dist[y] == -1:
dist[y] = dist[x] + 1
queue.append(y)
return [dist[x] if dist[x] != -1 else default for x in range(N)]
#最短路
def shortest_path(self, u, v):
""" u から v への最短路を求める (存在しない場合は None). """
if u == v:
return [u]
from collections import deque
prev = [-1] * self.order()
prev[u] = u
queue = deque([u])
while queue:
x = queue.popleft()
for y in self.adjacent[x]:
if prev[x] != -1:
continue
prev[y] = x
queue.append(y)
if y != v:
continue
path = [v]
a = v
while a != u:
a = prev[a]
path.append(a)
return path[::-1]
return None
def edge_yielder(self):
u = [0] * len(self.edge_alive); v = [0] * len(self.edge_alive)
for x in range(self.order()):
adj = self.adjacent[x]
ids = self.edge_ids[x]
for k in range(len(adj)):
id = ids[k]
u[id] = min(x, adj[k])
v[id] = max(x, adj[k])
for id in range(len(self.edge_alive)):
if self.edge_alive[id]:
yield (u[id], v[id])
def edge_yielder_with_index(self):
u = [0] * len(self.edge_alive); v = [0] * len(self.edge_alive)
for x in range(self.order()):
adj = self.adjacent[x]
ids = self.edge_ids[x]
for k in range(len(adj)):
id = ids[k]
u[id] = min(x, adj[k])
v[id] = max(x, adj[k])
for id in range(len(self.edge_alive)):
if self.edge_alive[id]:
yield (id, u[id], v[id])
def Lowlink(G: Graph, 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 G.neighborhood(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: Graph):
""" G にある橋の id を列挙する.
G: Graph
"""
ord, low = Lowlink(G)
return [id for id, u, v in G.edge_yielder_with_index() if (ord[u] < low[v]) or (ord[v] < low[u])]
#連結成分に分解
def Connected_Component_Decomposition(G: Graph, mode = 0):
""" 連結成分毎に分解する.
G: Graph
mode:0 → 連結成分, 1 → 連結成分番号, 2 → (連結成分, 連結成分番号)"""
comp_id = [-1] * G.order()
comps = []
def dfs(start, id):
stack = [start]
comp_id[start] = id
comp = []
while stack:
x = stack.pop()
comp.append(x)
for y in G.neighborhood(x):
if comp_id[y] == -1:
comp_id[y] = id
stack.append(y)
comps.append(comp)
id = 0
for x in range(G.order()):
if comp_id[x] == -1:
dfs(x, id)
id += 1
if mode == 0:
return comps
elif mode == 1:
return comp_id
elif mode == 2:
return (comps, comp_id)
#==================================================
def solve():
N, M, Q = map(int, input().split())
G = Graph(N + 1)
for j in range(M):
u, v = map(int, input().split())
G.add_edge(u, v)
bridges = set(Bridge(G))
H = Graph(N + 1)
for j, u, v in G.edge_yielder_with_index():
if j in bridges:
H.add_edge(u, v)
comp_id = Connected_Component_Decomposition(H, 1)
ans = [False] * Q
for q in range(Q):
x, y = map(int, input().split())
ans[q] = (comp_id[x] == comp_id[y])
return ans
#==================================================
import sys
input=sys.stdin.readline
write=sys.stdout.write
write("\n".join(map(str, ["Yes" if ans else "No" for ans in solve()])))