結果
| 問題 |
No.1983 [Cherry 4th Tune C] 南の島のマーメイド
|
| コンテスト | |
| ユーザー |
 lam6er
|
| 提出日時 | 2025-04-15 21:03:15 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,810 bytes |
| コンパイル時間 | 232 ms |
| コンパイル使用メモリ | 82,028 KB |
| 実行使用メモリ | 464,936 KB |
| 最終ジャッジ日時 | 2025-04-15 21:09:09 |
| 合計ジャッジ時間 | 48,564 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 39 TLE * 1 -- * 1 |
ソースコード
import sys
from sys import stdin
from sys import setrecursionlimit
from collections import defaultdict, deque
setrecursionlimit(1 << 25)
def main():
sys.setrecursionlimit(1 << 25)
input = sys.stdin.read
data = input().split()
idx = 0
N = int(data[idx]); idx +=1
M = int(data[idx]); idx +=1
Q = int(data[idx]); idx +=1
edges = []
adj = [[] for _ in range(N+1)]
for _ in range(M):
u = int(data[idx]); idx +=1
v = int(data[idx]); idx +=1
edges.append((u, v))
adj[u].append(v)
adj[v].append(u)
# Find bridges using Tarjan's algorithm
bridges = set()
visited = [False] * (N + 1)
disc = [0] * (N + 1)
low = [0] * (N + 1)
time_counter = [1]
parent = [-1] * (N + 1)
def tarjan(u):
disc[u] = low[u] = time_counter[0]
time_counter[0] += 1
visited[u] = True
for v in adj[u]:
if not visited[v]:
parent[v] = u
tarjan(v)
low[u] = min(low[u], low[v])
if low[v] > disc[u]:
bridges.add((u, v))
bridges.add((v, u))
elif v != parent[u]:
low[u] = min(low[u], disc[v])
for u in range(1, N+1):
if not visited[u]:
tarjan(u)
# Build the bridge forest
bridge_adj = [[] for _ in range(N+1)]
for u, v in edges:
if (u, v) in bridges:
bridge_adj[u].append(v)
bridge_adj[v].append(u)
# Assign component IDs in the bridge forest
comp_id = [0] * (N + 1)
current_comp = 0
visited = [False] * (N + 1)
for u in range(1, N+1):
if not visited[u]:
current_comp += 1
q = deque()
q.append(u)
visited[u] = True
comp_id[u] = current_comp
while q:
node = q.popleft()
for v in bridge_adj[node]:
if not visited[v]:
visited[v] = True
comp_id[v] = current_comp
q.append(v)
# Check connectivity in the original graph using BFS (or DSU would be better, but for brevity)
original_comp = [0] * (N + 1)
current_original_comp = 0
visited = [False] * (N + 1)
for u in range(1, N+1):
if not visited[u]:
current_original_comp += 1
q = deque()
q.append(u)
visited[u] = True
original_comp[u] = current_original_comp
while q:
node = q.popleft()
for v in adj[node]:
if not visited[v]:
visited[v] = True
original_comp[v] = current_original_comp
q.append(v)
# Preprocess parent and depth for LCA in bridge forest
parent_lca = [ [-1]*(20) for _ in range(N+1) ]
depth = [0]*(N+1)
visited = [False]*(N+1)
for u in range(1, N+1):
if not visited[u] and comp_id[u] != 0:
q = deque()
q.append(u)
visited[u] = True
parent_lca[u][0] = -1
while q:
node = q.popleft()
for v in bridge_adj[node]:
if not visited[v]:
visited[v] = True
depth[v] = depth[node] + 1
parent_lca[v][0] = node
q.append(v)
# Preprocess binary lifting table
for k in range(1, 20):
for u in range(1, N+1):
if parent_lca[u][k-1] != -1:
parent_lca[u][k] = parent_lca[parent_lca[u][k-1]][k-1]
else:
parent_lca[u][k] = -1
def lca(u, v):
if depth[u] < depth[v]:
u, v = v, u
for k in range(19, -1, -1):
if depth[u] - (1 << k) >= depth[v]:
u = parent_lca[u][k]
if u == v:
return u
for k in range(19, -1, -1):
if parent_lca[u][k] != -1 and parent_lca[u][k] != parent_lca[v][k]:
u = parent_lca[u][k]
v = parent_lca[v][k]
return parent_lca[u][0]
def get_path(u, ancestor):
path = []
while u != ancestor:
path.append(u)
u = parent_lca[u][0]
path.append(ancestor)
return path
# Collect non-bridge edges
non_bridge_edges = []
for u, v in edges:
if (u, v) not in bridges and (v, u) not in bridges:
non_bridge_edges.append((u, v))
# Build adjacency list for non-bridge edges
non_bridge_adj = defaultdict(set)
for u, v in non_bridge_edges:
non_bridge_adj[u].add(v)
non_bridge_adj[v].add(u)
# Process queries
output = []
for _ in range(Q):
x = int(data[idx]); idx +=1
y = int(data[idx]); idx +=1
if original_comp[x] != original_comp[y]:
output.append("No")
continue
if comp_id[x] != comp_id[y]:
output.append("No")
continue
# Find LCA in bridge forest
ancestor = lca(x, y)
path_x = get_path(x, ancestor)
path_y = get_path(y, ancestor)
path = path_x[:-1] + path_y[::-1]
# Check if any non-bridge edge exists between nodes in path
found = False
path_set = set(path)
for u in path:
for v in non_bridge_adj[u]:
if v in path_set and v != parent_lca[u][0] and u != parent_lca[v][0]:
found = True
break
if found:
break
if found:
output.append("No")
else:
output.append("Yes")
print('\n'.join(output))
if __name__ == "__main__":
main()