結果
| 問題 |
No.1326 ふたりのDominator
|
| ユーザー |
 lam6er
|
| 提出日時 | 2025-03-31 17:45:29 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,864 bytes |
| コンパイル時間 | 243 ms |
| コンパイル使用メモリ | 82,396 KB |
| 実行使用メモリ | 482,644 KB |
| 最終ジャッジ日時 | 2025-03-31 17:46:26 |
| 合計ジャッジ時間 | 13,033 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 19 TLE * 1 -- * 4 |
ソースコード
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 = int(input[ptr]); ptr +=1
M = int(input[ptr]); ptr +=1
edges = [[] for _ in range(N+1)]
for _ in range(M):
u = int(input[ptr]); ptr +=1
v = int(input[ptr]); ptr +=1
edges[u].append(v)
edges[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))
# Low-Link algorithm to find articulation points and biconnected components
order = [0] * (N + 1)
low = [0] * (N + 1)
visited = [False] * (N + 1)
is_articulation = [False] * (N + 1)
graph = edges
stack = []
bc_components = []
index = 1
parent = [0] * (N + 1)
def dfs(u):
nonlocal index
children = 0
visited[u] = True
order[u] = low[u] = index
index +=1
for v in graph[u]:
if not visited[v]:
stack.append((u, v))
parent[v] = u
children +=1
dfs(v)
low[u] = min(low[u], low[v])
if (parent[u] == 0 and children >= 2) or (parent[u] != 0 and low[v] >= order[u]):
is_articulation[u] = True
comp = []
while True:
e = stack.pop()
comp.append(e)
if e == (u, v):
break
bc_components.append(comp)
elif v != parent[u] and order[v] < order[u]:
low[u] = min(low[u], order[v])
stack.append((u, v))
if parent[u] == 0 and children == 0:
bc_components.append([(u, v)])
for u in range(1, N+1):
if not visited[u]:
dfs(u)
if stack:
comp = []
while stack:
e = stack.pop()
comp.append(e)
bc_components.append(comp)
articulation = [i for i in range(N+1) if is_articulation[i]]
# Build Block-Cut Tree
vertex_to_block = defaultdict(list)
for i, comp in enumerate(bc_components):
nodes = set()
for u, v in comp:
nodes.add(u)
nodes.add(v)
for u in nodes:
vertex_to_block[u].append(i)
block_to_artics = defaultdict(set)
artics_to_blocks = defaultdict(set)
for i, comp in enumerate(bc_components):
nodes = set()
for u, v in comp:
nodes.add(u)
nodes.add(v)
for u in nodes:
if is_articulation[u]:
block_to_artics[i].add(u)
artics_to_blocks[u].add(i)
node_count = len(bc_components) + len(articulation)
node_id = 0
block_ids = {}
for i in range(len(bc_components)):
block_ids[i] = node_id
node_id +=1
artic_ids = {a: node_id + i for i, a in enumerate(articulation)}
node_id += len(articulation)
block_adj = [[] for _ in range(node_count)]
artic_adj = [[] for _ in range(node_count)]
for art in articulation:
a_node = artic_ids[art]
for blk in artics_to_blocks[art]:
b_node = block_ids[blk]
block_adj[a_node].append(b_node)
block_adj[b_node].append(a_node)
artic_adj[a_node].append(b_node)
artic_adj[b_node].append(a_node)
parent_block = [-1 for _ in range(node_count)]
depth = [0]*node_count
queue = deque()
LOG = 20
up = [[-1]*node_count for _ in range(LOG)]
if node_count > 0:
root = 0
queue.append(root)
parent_block[root] = -1
up[0][root] = -1
depth[root] = 0
while queue:
u = queue.popleft()
for v in block_adj[u]:
if parent_block[v] == -1 and v != parent_block[u]:
parent_block[v] = u
depth[v] = depth[u] +1
up[0][v] = u
queue.append(v)
for k in range(1, LOG):
for v in range(node_count):
if up[k-1][v] != -1:
up[k][v] = up[k-1][up[k-1][v]]
def lca(u, v):
if depth[u] < depth[v]:
u, v = v, u
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_block[u]
def get_path(u, v):
res = []
anc = lca(u, v)
while u != anc:
res.append(u)
u = parent_block[u]
res.append(anc)
temp = []
while v != anc:
temp.append(v)
v = parent_block[v]
res += reversed(temp)
return res
def get_block_cut_node(v):
if is_articulation[v]:
return artic_ids[v]
else:
return block_ids[vertex_to_block[v][0]]
ans = []
for x, y in queries:
if x == y:
ans.append(0)
continue
node_x = get_block_cut_node(x)
node_y = get_block_cut_node(y)
if node_x == node_y:
ans.append(0)
continue
path = get_path(node_x, node_y)
count = 0
for n in path:
if n >= len(bc_components):
art = articulation[n - len(bc_components)]
if art != x and art != y:
count +=1
ans.append(count)
print('\n'.join(map(str, ans)))
if __name__ == "__main__":
main()