結果
| 問題 |
No.1326 ふたりのDominator
|
| ユーザー |
 lam6er
|
| 提出日時 | 2025-03-26 15:47:26 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,758 bytes |
| コンパイル時間 | 166 ms |
| コンパイル使用メモリ | 82,252 KB |
| 実行使用メモリ | 186,652 KB |
| 最終ジャッジ日時 | 2025-03-26 15:48:35 |
| 合計ジャッジ時間 | 14,433 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| 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, M = int(input[ptr]), int(input[ptr+1])
ptr +=2
edges = []
for _ in range(M):
u = int(input[ptr])-1
v = int(input[ptr+1])-1
edges.append((u, v))
ptr +=2
Q = int(input[ptr])
ptr +=1
queries = []
for _ in range(Q):
x = int(input[ptr])-1
y = int(input[ptr+1])-1
queries.append((x, y))
ptr +=2
graph = [[] for _ in range(N)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
# Find articulation points and biconnected components
order = [0]*N
low = [0]*N
used = [0]*N
articulations = [0]*N
parent = [-1]*N
bc_edges = []
stack = []
bc_id = 0
bc_vert_to_bc = defaultdict(list)
bc_components = []
current_edge = 0
time = 0
def dfs(u):
nonlocal time, current_edge
used[u] = 1
order[u] = low[u] = time
time +=1
children = 0
for v in graph[u]:
if v == parent[u]:
continue
if not used[v]:
stack.append((u, v))
parent[v] = u
children +=1
dfs(v)
low[u] = min(low[u], low[v])
if (parent[u] == -1 and children >=2) or (parent[u] != -1 and low[v] >= order[u]):
articulations[u] = 1
if low[v] >= order[u]:
component = []
while True:
e = stack.pop()
component.append(e)
if e == (u, v):
break
bc_components.append(component)
current_edge +=1
elif order[v] < order[u]:
low[u] = min(low[u], order[v])
stack.append((u, v))
for u in range(N):
if not used[u]:
dfs(u)
bc_vert = [[] for _ in range(len(bc_components))]
bc_edges = [[] for _ in range(len(bc_components))]
for i, component in enumerate(bc_components):
verts = set()
for u, v in component:
verts.add(u)
verts.add(v)
for v in verts:
bc_vert_to_bc[v].append(i)
bc_vert[i] = list(verts)
bc_edges[i] = component
block_to_artics = defaultdict(set)
artics_to_blocks = defaultdict(set)
for i in range(len(bc_components)):
comp = bc_vert[i]
artics = set()
for v in comp:
if articulations[v]:
artics.add(v)
for a in artics:
block_to_artics[i].add(a)
artics_to_blocks[a].add(i)
block_tree = defaultdict(list)
node_count = 0
block_node = {}
art_node = {}
for a in artics_to_blocks:
art_node[a] = node_count
node_count +=1
for b in range(len(bc_components)):
block_node[b] = node_count
node_count +=1
for a, blocks in artics_to_blocks.items():
a_node = art_node[a]
for b in blocks:
b_node = block_node[b]
block_tree[a_node].append(b_node)
block_tree[b_node].append(a_node)
for b in range(len(bc_components)):
b_node = block_node[b]
arts = block_to_artics[b]
for a in arts:
a_node = art_node[a]
if a_node not in block_tree[b_node]:
block_tree[b_node].append(a_node)
block_tree[a_node].append(b_node)
B = node_count
LOG = 20
parent_table = [[-1]*B for _ in range(LOG)]
depth = [0]*B
is_artic_node = [False]*B
for a in art_node.values():
is_artic_node[a] = True
for b in block_node.values():
is_artic_node[b] = False
visited = [False]*B
for root in range(B):
if not visited[root]:
q = deque()
q.append(root)
visited[root] = True
parent_table[0][root] = -1
depth[root] = 0
while q:
u = q.popleft()
for v in block_tree[u]:
if not visited[v]:
visited[v] = True
parent_table[0][v] = u
depth[v] = depth[u] +1
q.append(v)
for k in range(1, LOG):
for v in range(B):
if parent_table[k-1][v] != -1:
parent_table[k][v] = parent_table[k-1][parent_table[k-1][v]]
else:
parent_table[k][v] = -1
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 = parent_table[k][u]
if u == v:
return u
for k in range(LOG-1, -1, -1):
if parent_table[k][u] != parent_table[k][v]:
u = parent_table[k][u]
v = parent_table[k][v]
return parent_table[0][u]
def get_path_arts(u, l, exclude_x, x_node, exclude_y, y_node):
res = 0
while u != l:
if is_artic_node[u]:
if exclude_x and u == x_node:
pass
elif exclude_y and u == y_node:
pass
else:
res +=1
u = parent_table[0][u]
return res
for q in range(Q):
x, y = queries[q]
if x == y:
print(0)
continue
x_blocks = bc_vert_to_bc.get(x, [])
y_blocks = bc_vert_to_bc.get(y, [])
common = False
x_set = set(x_blocks)
for bl in y_blocks:
if bl in x_set:
common = True
break
if common:
print(0)
continue
if len(x_blocks) ==0 or len(y_blocks) ==0:
print(0)
continue
if articulations[x]:
x_node = art_node[x]
else:
x_block = x_blocks[0]
x_node = block_node[x_block]
if articulations[y]:
y_node = art_node[y]
else:
y_block = y_blocks[0]
y_node = block_node[y_block]
l = lca(x_node, y_node)
cnt = 0
u = x_node
cnt += get_path_arts(u, l, True, x_node, False, -1)
v = y_node
cnt += get_path_arts(v, l, False, -1, True, y_node)
if is_artic_node[l]:
if l == x_node:
pass
elif l == y_node:
pass
else:
cnt +=1
print(cnt)
if __name__ == "__main__":
main()