結果
| 問題 |
No.1326 ふたりのDominator
|
| コンテスト | |
| ユーザー |
 lam6er
|
| 提出日時 | 2025-04-15 23:35:14 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,472 bytes |
| コンパイル時間 | 145 ms |
| コンパイル使用メモリ | 82,012 KB |
| 実行使用メモリ | 79,548 KB |
| 最終ジャッジ日時 | 2025-04-15 23:36:12 |
| 合計ジャッジ時間 | 5,042 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 11 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
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
# Step 1: Find articulation points and blocks using Tarjan's algorithm
index = 1
ord_ = [0]*(N+1)
low = [0]*(N+1)
is_artic = [False]*(N+1)
stack = []
blocks = []
block_id = 0
belongs_to_block = [[] for _ in range(N+1)]
belongs_to_art = [[] for _ in range(N+1)]
def tarjan(u, parent):
nonlocal index
ord_[u] = low[u] = index
index +=1
children = 0
for v in adj[u]:
if ord_[v] == 0:
stack.append((u, v))
children +=1
tarjan(v, u)
low[u] = min(low[u], low[v])
if (parent == -1 and children > 1) or (parent != -1 and low[v] >= ord_[u]):
is_artic[u] = True
block = []
while True:
edge = stack.pop()
block.append(edge)
if edge == (u, v) or edge == (v, u):
break
blocks.append(block)
elif v != parent and ord_[v] < ord_[u]:
stack.append((u, v))
low[u] = min(low[u], ord_[v])
if parent == -1 and children == 0:
is_artic[u] = True
for u in range(1, N+1):
if ord_[u] == 0:
tarjan(u, -1)
if stack:
block = []
while stack:
edge = stack.pop()
block.append(edge)
blocks.append(block)
art_nodes = [u for u in range(1, N+1) if is_artic[u]]
block_to_arts = defaultdict(list)
art_to_blocks = defaultdict(list)
edge_set = [set() for _ in range(N+1)]
for b in blocks:
vertices = set()
for u, v in b:
vertices.add(u)
vertices.add(v)
arts_in_block = [u for u in vertices if is_artic[u]]
for art in arts_in_block:
block_to_arts[id(b)].append(art)
art_to_blocks[art].append(id(b))
block_vertices = defaultdict(set)
for i, b in enumerate(blocks):
for u, v in b:
block_vertices[id(b)].add(u)
block_vertices[id(b)].add(v)
node_map = {}
block_nodes = []
art_nodes_list = []
node_type = {} # 'block' or 'art'
node_id_counter = 0
block_id_to_node = {}
for b in blocks:
bid = id(b)
block_id_to_node[bid] = node_id_counter
node_map[node_id_counter] = ('block', bid)
node_type[node_id_counter] = 'block'
block_nodes.append(node_id_counter)
node_id_counter +=1
art_node_to_node = {}
for art in art_nodes:
art_node_to_node[art] = node_id_counter
node_map[node_id_counter] = ('art', art)
node_type[node_id_counter] = 'art'
art_nodes_list.append(node_id_counter)
node_id_counter +=1
block_tree_adj = [[] for _ in range(node_id_counter)]
for art in art_nodes:
art_node = art_node_to_node[art]
for bid in art_to_blocks[art]:
block_node = block_id_to_node[bid]
block_tree_adj[block_node].append(art_node)
block_tree_adj[art_node].append(block_node)
vertex_to_node = [0]*(N+1)
for u in range(1, N+1):
if is_artic[u]:
vertex_to_node[u] = art_node_to_node[u]
else:
found = False
for bid in block_vertices:
if u in block_vertices[bid]:
vertex_to_node[u] = block_id_to_node[bid]
found = True
break
if not found:
pass
LOG = 20
parent = [[-1]*node_id_counter for _ in range(LOG)]
depth = [0]*node_id_counter
depth_art = [0]*node_id_counter
visited = [False]*node_id_counter
def dfs(u, p, d, cnt_art):
visited[u] = True
parent[0][u] = p
depth[u] = d
current_cnt = cnt_art
if node_type[u] == 'art':
current_cnt +=1
depth_art[u] = current_cnt
for v in block_tree_adj[u]:
if not visited[v] and v != p:
dfs(v, u, d+1, current_cnt)
root = block_nodes[0] if block_nodes else art_nodes_list[0]
dfs(root, -1, 0, 0)
for k in range(1, LOG):
for v in range(node_id_counter):
if parent[k-1][v] != -1:
parent[k][v] = parent[k-1][parent[k-1][v]]
def lca(u, v):
if depth[u] < depth[v]:
u, v = v, u
for k in reversed(range(LOG)):
if parent[k][u] != -1 and depth[u] - (1 << k) >= depth[v]:
u = parent[k][u]
if u == v:
return u
for k in reversed(range(LOG)):
if parent[k][u] != -1 and parent[k][u] != parent[k][v]:
u = parent[k][u]
v = parent[k][v]
return parent[0][u]
def count_art_nodes(u, v, lca_node):
cnt_u = depth_art[u] - depth_art[lca_node]
cnt_v = depth_art[v] - depth_art[lca_node]
total = cnt_u + cnt_v
if node_type[lca_node] == 'art':
total +=1
return total
for x, y in queries:
if x == y:
print(0)
continue
u = x
v_node = y
u_node_id = vertex_to_node[u]
v_node_id = vertex_to_node[v_node]
if u_node_id == v_node_id:
print(0)
continue
l = lca(u_node_id, v_node_id)
cnt = count_art_nodes(u_node_id, v_node_id, l)
if node_type[u_node_id] == 'art':
art_value = node_map[u_node_id][1]
if art_value == x or art_value == y:
cnt -=1
if node_type[v_node_id] == 'art':
art_value = node_map[v_node_id][1]
if art_value == x or art_value == y:
cnt -=1
print(max(0, cnt))
if __name__ == '__main__':
main()