結果
| 問題 |
No.1326 ふたりのDominator
|
| コンテスト | |
| ユーザー |
 lam6er
|
| 提出日時 | 2025-04-15 23:37:06 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 6,771 bytes |
| コンパイル時間 | 175 ms |
| コンパイル使用メモリ | 81,812 KB |
| 実行使用メモリ | 311,856 KB |
| 最終ジャッジ日時 | 2025-04-15 23:38:06 |
| 合計ジャッジ時間 | 13,098 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | RE * 1 |
| other | AC * 3 RE * 21 |
ソースコード
import sys
from sys import stdin
from collections import defaultdict, deque
sys.setrecursionlimit(1 << 25)
def main():
input = sys.stdin.read().split()
ptr = 0
N, M = int(input[ptr]), int(input[ptr+1])
ptr +=2
graph = [[] for _ in range(N+1)]
for _ in range(M):
u = int(input[ptr])
v = int(input[ptr+1])
graph[u].append(v)
graph[v].append(u)
ptr +=2
Q = int(input[ptr])
ptr +=1
queries = []
for _ in range(Q):
x = int(input[ptr])
y = int(input[ptr+1])
queries.append((x, y))
ptr +=2
# Biconnected components decomposition
ord_ = [-1] * (N + 1)
low = [-1] * (N + 1)
is_art = [False] * (N + 1)
stack = []
blocks = []
index = 0
def dfs(v, parent):
nonlocal index
ord_[v] = index
low[v] = index
index +=1
children = 0
for to in graph[v]:
if to == parent:
continue
if ord_[to] == -1:
stack.append((v, to))
children +=1
dfs(to, v)
low[v] = min(low[v], low[to])
if (parent == -1 and children >=2) or (parent != -1 and low[to] >= ord_[v]):
is_art[v] = True
block = []
while True:
e = stack.pop()
block.append(e)
if e == (v, to):
break
blocks.append(block)
elif ord_[to] < ord_[v]:
stack.append((v, to))
low[v] = min(low[v], ord_[to])
if parent == -1 and children ==0:
blocks.append([(v, to) for to in graph[v]])
for v in range(1, N+1):
if ord_[v] == -1:
dfs(v, -1)
if stack:
block = []
while stack:
e = stack.pop()
block.append(e)
if block:
blocks.append(block)
art_nodes = set(v for v in range(1, N+1) if is_art[v])
block_edges = defaultdict(set)
vertex_to_block = defaultdict(list)
block_id = 0
block_to_vertices = []
for blk in blocks:
vertices = set()
for u, v in blk:
vertices.add(u)
vertices.add(v)
block_to_vertices.append(vertices)
for v in vertices:
vertex_to_block[v].append(block_id)
block_id +=1
block_tree = defaultdict(list)
block_id_to_node = {}
node_counter = 0
for bid in range(len(blocks)):
block_node = - (bid +1)
block_id_to_node[bid] = block_node
vertices = block_to_vertices[bid]
arts_in_block = []
for v in vertices:
if is_art[v]:
arts_in_block.append(v)
for art in arts_in_block:
block_tree[block_node].append(art)
block_tree[art].append(block_node)
belongs_to = [0]*(N+1)
for v in range(1, N+1):
if is_art[v]:
belongs_to[v] = v
else:
for bid in vertex_to_block[v]:
belongs_to[v] = block_id_to_node[bid]
break
all_nodes = set()
for nodes in block_tree:
all_nodes.add(nodes)
for nodes in block_tree.values():
all_nodes.update(nodes)
all_nodes = list(all_nodes)
node_to_idx = {node: i for i, node in enumerate(all_nodes)}
idx_to_node = {i: node for i, node in enumerate(all_nodes)}
num_nodes = len(all_nodes)
parent = [[-1]*20 for _ in range(num_nodes)]
depth = [0]*num_nodes
art_count = [0]*num_nodes
visited = [False]*num_nodes
def is_art_node(node):
return node > 0
for root in all_nodes:
if not visited[node_to_idx[root]]:
q = deque()
q.append((root, -1, 0, 0))
while q:
node, p_node, d, cnt = q.popleft()
idx = node_to_idx[node]
if visited[idx]:
continue
visited[idx] = True
depth[idx] = d
parent[idx][0] = node_to_idx[p_node] if p_node != -1 else -1
new_cnt = cnt + (1 if is_art_node(node) else 0)
art_count[idx] = new_cnt
for neighbor in block_tree[node]:
n_idx = node_to_idx[neighbor]
if not visited[n_idx]:
q.append((neighbor, node, d+1, new_cnt))
for k in range(1, 20):
for i in range(num_nodes):
if parent[i][k-1] != -1:
parent[i][k] = parent[parent[i][k-1]][k-1]
else:
parent[i][k] = -1
def lca(u_idx, v_idx):
if depth[u_idx] < depth[v_idx]:
u_idx, v_idx = v_idx, u_idx
for k in range(19, -1, -1):
if parent[u_idx][k] != -1 and depth[parent[u_idx][k]] >= depth[v_idx]:
u_idx = parent[u_idx][k]
if u_idx == v_idx:
return u_idx
for k in range(19, -1, -1):
if parent[u_idx][k] != parent[v_idx][k]:
u_idx = parent[u_idx][k]
v_idx = parent[v_idx][k]
return parent[u_idx][0]
def get_art_num(u_node, v_node):
u_idx = node_to_idx[u_node]
v_idx = node_to_idx[v_node]
l = lca(u_idx, v_idx)
total = art_count[u_idx] + art_count[v_idx] - 2 * art_count[l]
if is_art_node(idx_to_node[l]):
total +=1
return total
def is_ancestor(a_idx, b_idx):
return lca(b_idx, a_idx) == a_idx
def is_on_path(u_node, v_node, a_node):
a_idx = node_to_idx[a_node]
u_idx = node_to_idx[u_node]
v_idx = node_to_idx[v_node]
luv_idx = lca(u_idx, v_idx)
lau_idx = lca(u_idx, a_idx)
lav_idx = lca(v_idx, a_idx)
if lau_idx != a_idx and lav_idx != a_idx:
return False
if lau_idx == a_idx:
return is_ancestor(luv_idx, a_idx)
else:
return is_ancestor(luv_idx, a_idx)
for x, y in queries:
if x == y:
print(0)
continue
u = belongs_to[x]
v_node = belongs_to[y]
if u == v_node:
print(0)
continue
total = get_art_num(u, v_node)
if is_art[x]:
a_node = x
a_idx = node_to_idx[a_node]
u_idx = node_to_idx[u]
v_idx = node_to_idx[v_node]
if is_on_path(u, v_node, a_node):
total -=1
if is_art[y]:
a_node = y
if is_on_path(u, v_node, a_node):
total -=1
print(max(0, total))
if __name__ == '__main__':
main()