結果
| 問題 |
No.1983 [Cherry 4th Tune C] 南の島のマーメイド
|
| コンテスト | |
| ユーザー |
 lam6er
|
| 提出日時 | 2025-03-31 17:37:38 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,827 bytes |
| コンパイル時間 | 235 ms |
| コンパイル使用メモリ | 82,536 KB |
| 実行使用メモリ | 366,132 KB |
| 最終ジャッジ日時 | 2025-03-31 17:39:10 |
| 合計ジャッジ時間 | 46,883 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 16 WA * 25 |
ソースコード
import sys
from sys import stdin
from collections import defaultdict, deque
sys.setrecursionlimit(1 << 25)
def main():
input = sys.stdin.read
data = input().split()
ptr = 0
N, M, Q = map(int, data[ptr:ptr+3])
ptr += 3
edges = []
adj = [[] for _ in range(N+1)]
for _ in range(M):
u = int(data[ptr])
v = int(data[ptr+1])
ptr += 2
adj[u].append((v, len(edges)))
adj[v].append((u, len(edges)))
edges.append((u, v))
# Find all bridges using Tarjan's algorithm (iterative)
bridges = set()
index = 0
indices = [0]*(N+1)
low = [0]*(N+1)
visited = [False]*(N+1)
edge_stack = []
for start in range(1, N+1):
if not visited[start]:
stack = [(start, -1, -1, False)]
while stack:
node, parent, edge_id, is_processed = stack.pop()
if is_processed:
if parent != -1:
low[parent] = min(low[parent], low[node])
if low[node] > indices[parent]:
bridges.add(edge_id)
else:
if visited[node]:
continue
visited[node] = True
indices[node] = index
low[node] = index
index += 1
stack.append((node, parent, edge_id, True))
for neighbor, eid in adj[node]:
if not visited[neighbor]:
stack.append((neighbor, node, eid, False))
elif eid != edge_id and neighbor != parent:
low[node] = min(low[node], indices[neighbor])
# Assign 2-edge-connected components (BFS avoiding bridges)
component = [0]*(N+1)
comp_id = 0
visited = [False]*(N+1)
for u in range(1, N+1):
if not visited[u]:
comp_id += 1
q = deque()
q.append(u)
visited[u] = True
component[u] = comp_id
while q:
v = q.popleft()
for neighbor, eid in adj[v]:
if not visited[neighbor] and eid not in bridges:
visited[neighbor] = True
component[neighbor] = comp_id
q.append(neighbor)
# DSU for original graph to check connectivity
parent = list(range(N+1))
def find(u):
while parent[u] != u:
parent[u] = parent[parent[u]]
u = parent[u]
return u
def union(u, v):
u_root = find(u)
v_root = find(v)
if u_root != v_root:
parent[v_root] = u_root
for u, v in edges:
union(u, v)
# Build bridge tree
bt_adj = defaultdict(list)
comp_nodes = defaultdict(list)
comp_size = defaultdict(int)
for u in range(1, N+1):
c = component[u]
comp_nodes[c].append(u)
comp_size[c] += 1
for eid in bridges:
u, v = edges[eid]
c1 = component[u]
c2 = component[v]
bt_adj[c1].append(c2)
bt_adj[c2].append(c1)
LOG = 20
up = [[0]*(comp_id+1) for _ in range(LOG)]
has_large = [[False]*(comp_id+1) for _ in range(LOG)]
depth = [0]*(comp_id+1)
def build_binary_lifting(c_root, tree):
q = deque()
q.append((c_root, -1, 0))
up[0][c_root] = -1
depth[c_root] = 0
while q:
u, p, d = q.popleft()
for v in tree[u]:
if v != p and up[0][v] == 0:
up[0][v] = u
depth[v] = d + 1
q.append((v, u, d + 1))
for u in tree.keys():
if up[0][u] == 0:
up[0][u] = -1
up[0][c_root] = -1
for k in range(1, LOG):
for u in tree.keys():
if up[k-1][u] == -1:
up[k][u] = -1
has_large[k][u] = has_large[k-1][u]
else:
up[k][u] = up[k-1][up[k-1][u]]
has_large[k][u] = has_large[k-1][u] or has_large[k-1][up[k-1][u]]
for node in bt_adj.keys():
if up[0][node] == 0:
build_binary_lifting(node, bt_adj)
for c in comp_nodes:
k = comp_size[c] > 1
for i in range(LOG):
has_large[i][c] = k or (has_large[i][c] if up[i][c] != -1 else False)
def lca(u, v):
if depth[u] < depth[v]:
u, v = v, u
for k in reversed(range(LOG)):
if depth[u] - (1 << k) >= depth[v]:
u = up[k][u]
if u == v:
return u
for k in reversed(range(LOG)):
if up[k][u] != -1 and up[k][u] != up[k][v]:
u = up[k][u]
v = up[k][v]
return up[0][u]
def has_large_on_path(u, lca_node):
current = u
res = False
for k in reversed(range(LOG)):
if depth[current] - (1 << k) >= depth[lca_node]:
res |= has_large[k][current]
current = up[k][current]
return res
output = []
for _ in range(Q):
x = int(data[ptr])
y = int(data[ptr+1])
ptr +=2
if find(x) != find(y):
output.append("No")
continue
if x == y:
output.append("No")
continue
cx = component[x]
cy = component[y]
if cx == cy:
output.append("No")
continue
l = lca(cx, cy)
res1 = has_large_on_path(cx, l)
res2 = has_large_on_path(cy, l)
if res1 or res2:
output.append("No")
else:
output.append("Yes")
print('\n'.join(output))
if __name__ == "__main__":
main()