結果
| 問題 |
No.1326 ふたりのDominator
|
| ユーザー |
 gew1fw
|
| 提出日時 | 2025-06-12 20:21:05 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,638 bytes |
| コンパイル時間 | 245 ms |
| コンパイル使用メモリ | 82,148 KB |
| 実行使用メモリ | 269,012 KB |
| 最終ジャッジ日時 | 2025-06-12 20:21:31 |
| 合計ジャッジ時間 | 13,327 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 4 WA * 20 |
ソースコード
import sys
from collections import defaultdict, deque
def main():
sys.setrecursionlimit(1 << 25)
input = sys.stdin.read().split()
ptr = 0
N = int(input[ptr])
ptr += 1
M = int(input[ptr])
ptr += 1
adj = [[] for _ in range(N+1)]
for _ in range(M):
u = int(input[ptr])
ptr += 1
v = int(input[ptr])
ptr += 1
adj[u].append(v)
adj[v].append(u)
Q = int(input[ptr])
ptr += 1
queries = []
for _ in range(Q):
x = int(input[ptr])
ptr += 1
y = int(input[ptr])
ptr += 1
queries.append((x, y))
# Tarjan's algorithm to find articulation points and biconnected components
class Tarjan:
def __init__(self, adj, N):
self.adj = adj
self.N = N
self.disc = [0] * (N + 1)
self.low = [0] * (N + 1)
self.time = 1
self.articulation = [False] * (N + 1)
self.components = []
self.stack = []
self.parent = [0] * (N + 1)
self.visited = [False] * (N + 1)
def run(self):
for u in range(1, self.N + 1):
if not self.visited[u]:
self.dfs(u)
# Correct articulation points for root node
for u in range(1, self.N + 1):
if self.parent[u] == 0:
count = 0
for v in self.adj[u]:
if self.parent[v] == u:
count += 1
self.articulation[u] = count > 1
def dfs(self, u):
self.visited[u] = True
self.disc[u] = self.low[u] = self.time
self.time += 1
children = 0
for v in self.adj[u]:
if not self.visited[v]:
self.parent[v] = u
children += 1
self.stack.append((u, v))
self.dfs(v)
self.low[u] = min(self.low[u], self.low[v])
if self.low[v] >= self.disc[u]:
self.articulation[u] = True
comp = []
while True:
edge = self.stack.pop()
comp.append(edge)
if edge == (u, v):
break
self.components.append(comp)
elif v != self.parent[u] and self.disc[v] < self.disc[u]:
self.stack.append((u, v))
self.low[u] = min(self.low[u], self.disc[v])
# After exploring all children, check if root node
if self.parent[u] == 0:
self.articulation[u] = children > 1
tarjan = Tarjan(adj, N)
tarjan.run()
# Process components to find nodes and articulation points in each component
blocks = []
node_to_block = [0] * (N + 1) # for non-articulation nodes
block_id = 0
for comp in tarjan.components:
nodes = set()
for u, v in comp:
nodes.add(u)
nodes.add(v)
component_nodes = list(nodes)
component_articulations = [u for u in component_nodes if tarjan.articulation[u]]
blocks.append({
'id': block_id,
'nodes': component_nodes,
'articulations': component_articulations
})
for u in component_nodes:
if not tarjan.articulation[u]:
if node_to_block[u] == 0:
node_to_block[u] = block_id
block_id += 1
# Build BCT
bct_adj = defaultdict(list)
for block in blocks:
bid = block['id']
for a in block['articulations']:
bct_adj[bid].append(a)
bct_adj[a].append(bid)
# Determine root of BCT (block containing node 1, or node 1 if it's an articulation point)
if tarjan.articulation[1]:
root = 1
else:
root = node_to_block[1]
# BFS to compute sum_articulation, depth, and parent for LCA
max_bct_node = 0
for u in bct_adj:
if u > max_bct_node:
max_bct_node = u
for block in blocks:
if block['id'] > max_bct_node:
max_bct_node = block['id']
LOG = 20
up = [[-1] * (max_bct_node + 1) for _ in range(LOG)]
depth = [0] * (max_bct_node + 1)
sum_art = [0] * (max_bct_node + 1)
parent = [-1] * (max_bct_node + 1)
queue = deque([root])
visited = set([root])
sum_art[root] = 1 if (root <= N and tarjan.articulation[root]) else 0
depth[root] = 0
parent[root] = -1
while queue:
u = queue.popleft()
for v in bct_adj[u]:
if v not in visited:
visited.add(v)
parent[v] = u
depth[v] = depth[u] + 1
is_art = (v <= N and tarjan.articulation[v])
sum_art[v] = sum_art[u] + (1 if is_art else 0)
queue.append(v)
# Build binary lifting table
up[0] = parent
for k in range(1, LOG):
for u in range(max_bct_node + 1):
if up[k-1][u] != -1:
up[k][u] = up[k-1][up[k-1][u]]
else:
up[k][u] = -1
# LCA function
def lca(u, v):
if depth[u] < depth[v]:
u, v = v, u
# Bring u to the depth of v
for k in range(LOG-1, -1, -1):
if depth[u] - (1 << k) >= depth[v]:
u = up[k][u]
if u == v:
return u
for k in range(LOG-1, -1, -1):
if up[k][u] != -1 and up[k][u] != up[k][v]:
u = up[k][u]
v = up[k][v]
return parent[u]
# Process queries
for x, y in queries:
if x == y:
print(0)
continue
# Get x_node and y_node
x_node = x if tarjan.articulation[x] else node_to_block[x]
y_node = y if tarjan.articulation[y] else node_to_block[y]
if x_node == y_node:
print(0)
continue
# Compute LCA
lca_node = lca(x_node, y_node)
# Compute sum_articulation
sum_u = sum_art[x_node]
sum_v = sum_art[y_node]
sum_lca = sum_art[lca_node]
total = sum_u + sum_v - 2 * sum_lca
# Check if lca_node is an articulation point
if lca_node <= N and tarjan.articulation[lca_node]:
total += 1
# Subtract x and y's articulation points
answer = total - tarjan.articulation[x] - tarjan.articulation[y]
print(max(0, answer))
if __name__ == '__main__':
main()