結果
| 問題 |
No.1326 ふたりのDominator
|
| ユーザー |
 gew1fw
|
| 提出日時 | 2025-06-12 20:22:08 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 7,731 bytes |
| コンパイル時間 | 394 ms |
| コンパイル使用メモリ | 81,712 KB |
| 実行使用メモリ | 138,664 KB |
| 最終ジャッジ日時 | 2025-06-12 20:23:00 |
| 合計ジャッジ時間 | 6,177 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 9 RE * 2 TLE * 1 -- * 12 |
ソースコード
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
adj = [[] for _ in range(N+1)]
for _ in range(M):
u = int(input[ptr])
v = int(input[ptr+1])
adj[u].append(v)
adj[v].append(u)
ptr +=2
# Step 1: Find articulation points and biconnected components using Tarjan's algorithm
disc = [0]*(N+1)
low = [0]*(N+1)
time_counter = [1]
ap = [False]*(N+1)
parent = [0]*(N+1)
stack = []
bcc = []
block_edges_list = []
def tarjan(u):
disc[u] = low[u] = time_counter[0]
time_counter[0] +=1
children = 0
for v in adj[u]:
if disc[v] == 0:
parent[v] = u
stack.append((u, v))
children +=1
tarjan(v)
low[u] = min(low[u], low[v])
if (parent[u] == 0 and children >=2) or (parent[u] !=0 and low[v] >= disc[u]):
ap[u] = True
current_bcc = []
while True:
edge = stack.pop()
current_bcc.append(edge)
if edge == (u, v):
break
block_edges_list.append(current_bcc)
elif v != parent[u] and disc[v] < disc[u]:
stack.append((u, v))
low[u] = min(low[u], disc[v])
return
for u in range(1, N+1):
if disc[u] == 0:
tarjan(u)
if stack:
current_bcc = []
while stack:
edge = stack.pop()
current_bcc.append(edge)
block_edges_list.append(current_bcc)
# Collect all articulation points
articulation_points = set(u for u in range(1, N+1) if ap[u])
# Step 2: Build BC tree
# Assign each block and articulation point to a node in BC tree
# Create mappings
block_nodes = []
ap_nodes = []
block_id = 0
node_to_bc = {}
bc_tree_adj = defaultdict(list)
# Process each block
for bid, edges in enumerate(block_edges_list):
nodes = set()
for u, v in edges:
nodes.add(u)
nodes.add(v)
block_node = ('block', bid)
block_nodes.append(block_node)
# Connect to articulation points in this block
aps_in_block = set()
for node in nodes:
if ap[node]:
aps_in_block.add(node)
for ap_node in aps_in_block:
ap_bc_node = ('ap', ap_node)
bc_tree_adj[block_node].append(ap_bc_node)
bc_tree_adj[ap_bc_node].append(block_node)
# Process articulation points and their blocks
for u in articulation_points:
ap_bc_node = ('ap', u)
# Find all blocks that include this articulation point
for bid, edges in enumerate(block_edges_list):
nodes = set()
for x, y in edges:
nodes.add(x)
nodes.add(y)
if u in nodes:
block_node = ('block', bid)
if block_node not in bc_tree_adj[ap_bc_node]:
bc_tree_adj[ap_bc_node].append(block_node)
bc_tree_adj[block_node].append(ap_bc_node)
# Step 3: Assign each original node to BC node
node_to_bc = {}
# For non-articulation points, find their block
non_ap_block = {}
for bid, edges in enumerate(block_edges_list):
nodes = set()
for u, v in edges:
nodes.add(u)
nodes.add(v)
for node in nodes:
if not ap[node]:
if node not in non_ap_block:
non_ap_block[node] = ('block', bid)
# Step 4: Preprocess BC tree for LCA and art_count
# Convert BC tree nodes to unique identifiers
bc_nodes = set()
for node in bc_tree_adj:
bc_nodes.add(node)
bc_node_list = list(bc_nodes)
node_to_idx = {node: i for i, node in enumerate(bc_node_list)}
idx_to_node = {i: node for i, node in enumerate(bc_node_list)}
total_nodes = len(bc_node_list)
tree = [[] for _ in range(total_nodes)]
for node in bc_tree_adj:
idx = node_to_idx[node]
for neighbor in bc_tree_adj[node]:
neighbor_idx = node_to_idx[neighbor]
tree[idx].append(neighbor_idx)
# BFS to setup parent, depth, and art_count
LOG = 20
parent_lca = [[-1]*total_nodes for _ in range(LOG)]
depth = [0]*total_nodes
art_count = [0]*total_nodes
# Choose root as the first node (arbitrary)
root = 0
q = deque()
q.append(root)
parent_lca[0][root] = -1
visited = [False]*total_nodes
visited[root] = True
while q:
u = q.popleft()
for v in tree[u]:
if not visited[v]:
visited[v] = True
parent_lca[0][v] = u
depth[v] = depth[u] + 1
# art_count: if current node is articulation point, add 1
current_node = idx_to_node[v]
if current_node[0] == 'ap':
art_count[v] = art_count[u] + 1
else:
art_count[v] = art_count[u]
q.append(v)
# Fill parent_lca for binary lifting
for k in range(1, LOG):
for v in range(total_nodes):
if parent_lca[k-1][v] != -1:
parent_lca[k][v] = parent_lca[k-1][parent_lca[k-1][v]]
# LCA function
def lca(u, v):
if depth[u] < depth[v]:
u, v = v, u
# Bring u to the same depth as v
for k in range(LOG-1, -1, -1):
if depth[u] - (1 << k) >= depth[v]:
u = parent_lca[k][u]
if u == v:
return u
for k in range(LOG-1, -1, -1):
if parent_lca[k][u] != -1 and parent_lca[k][u] != parent_lca[k][v]:
u = parent_lca[k][u]
v = parent_lca[k][v]
return parent_lca[0][u]
# Function to get art count between two nodes
def get_art_count(u_idx, v_idx):
ancestor_idx = lca(u_idx, v_idx)
count = art_count[u_idx] + art_count[v_idx] - 2 * art_count[ancestor_idx]
ancestor_node = idx_to_node[ancestor_idx]
if ancestor_node[0] == 'ap':
count +=1
return count
# Process queries
Q = int(input[ptr])
ptr +=1
for _ in range(Q):
x = int(input[ptr])
y = int(input[ptr+1])
ptr +=2
if x == y:
print(0)
continue
# Get Bx and By
if x in articulation_points:
Bx = ('ap', x)
else:
if x not in non_ap_block:
print(0)
continue
Bx = non_ap_block[x]
if y in articulation_points:
By = ('ap', y)
else:
if y not in non_ap_block:
print(0)
continue
By = non_ap_block[y]
if Bx == By:
print(0)
continue
# Convert Bx and By to indices
if Bx not in node_to_idx or By not in node_to_idx:
print(0)
continue
u = node_to_idx[Bx]
v = node_to_idx[By]
# Get art count
cnt = get_art_count(u, v)
# Subtract x and y if they are articulation points
subtract = 0
if x in articulation_points:
subtract +=1
if y in articulation_points:
subtract +=1
ans = cnt - subtract
print(max(0, ans))
if __name__ == "__main__":
main()