結果
問題 |
No.1326 ふたりのDominator
|
ユーザー |
![]() |
提出日時 | 2025-06-12 20:23:08 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 5,723 bytes |
コンパイル時間 | 208 ms |
コンパイル使用メモリ | 81,896 KB |
実行使用メモリ | 702,684 KB |
最終ジャッジ日時 | 2025-06-12 20:23:51 |
合計ジャッジ時間 | 4,121 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 1 MLE * 1 -- * 22 |
ソースコード
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(N+1)] for _ in range(M): u = int(input[ptr]) v = int(input[ptr+1]) edges[u].append(v) edges[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 # Biconnected components decomposition low = [0]*(N+1) ord_ = [0]*(N+1) visited = [False]*(N+1) is_articulation = [False]*(N+1) stack = [] bc_components = [] parent = [0]*(N+1) child_count = [0]*(N+1) time_counter = [1] graph = edges def dfs(u): visited[u] = True ord_[u] = low[u] = time_counter[0] time_counter[0] +=1 for v in graph[u]: if v == parent[u]: continue if not visited[v]: parent[v] = u child_count[u] +=1 stack.append((u, v)) dfs(v) low[u] = min(low[u], low[v]) if (parent[u] == 0 and child_count[u] >=2) or (parent[u] !=0 and low[v] >= ord_[u]): is_articulation[u] = True comp = [] while True: e = stack.pop() comp.append(e) if e == (u, v): break bc_components.append(comp) else: if ord_[v] < ord_[u]: stack.append((u, v)) low[u] = min(low[u], ord_[v]) if parent[u] ==0 and child_count[u] ==0: bc_components.append([(parent[u], u)]) 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) node_id = 0 block_map = defaultdict(list) articulation_blocks = defaultdict(list) block_edges = defaultdict(list) vertex_to_block = defaultdict(list) for comp in bc_components: nodes = set() art_points = set() for u, v in comp: nodes.add(u) nodes.add(v) block_id = node_id node_id +=1 for u in nodes: if is_articulation[u]: art_points.add(u) else: block_map[block_id].append(u) vertex_to_block[u].append(block_id) for art in art_points: articulation_blocks[art].append(block_id) block_edges[block_id].append(art) block_edges[art].append(block_id) vertex_to_block[art].append(block_id) block_tree = defaultdict(list) for key in block_edges: for v in block_edges[key]: block_tree[key].append(v) LOG = 20 depth = defaultdict(int) up = defaultdict(lambda: defaultdict(int)) def build_lca(u, p, d): depth[u] = d up[u][0] = p for i in range(1, LOG): up[u][i] = up[up[u][i-1]][i-1] for v in block_tree[u]: if v != p: build_lca(v, u, d+1) root = next(iter(block_tree.keys()), None) if root is not None: build_lca(root, -1, 0) def lca(u, v): if depth[u] < depth[v]: u, v = v, u for i in range(LOG-1, -1, -1): if depth[u] - (1<<i) >= depth[v]: u = up[u][i] if u == v: return u for i in range(LOG-1, -1, -1): if up[u][i] != up[v][i]: u = up[u][i] v = up[v][i] return up[u][0] def get_path(u, a): path = [] while u != a: path.append(u) u = up[u][0] path.append(a) return path def get_block(x): if is_articulation[x]: return x else: return vertex_to_block[x][0] res = [] for x, y in queries: if x == y: res.append(0) continue x_blocks = [] if is_articulation[x]: x_blocks.append(x) for blk in articulation_blocks[x]: x_blocks.append(blk) else: x_blocks.append(vertex_to_block[x][0]) y_blocks = [] if is_articulation[y]: y_blocks.append(y) for blk in articulation_blocks[y]: y_blocks.append(blk) else: y_blocks.append(vertex_to_block[y][0]) found = False answer = 0 for xb in x_blocks: for yb in y_blocks: a = lca(xb, yb) path_x = get_path(xb, a) path_y = get_path(yb, a) total_path = path_x[:-1] + path_y[::-1] art_points = [] for node in total_path: if isinstance(node, int) and node <= N and is_articulation[node]: art_points.append(node) cnt = 0 for art in art_points: if art != x and art != y: cnt +=1 if cnt >0: answer = cnt found = True break if found: break res.append(answer if found else 0) for ans in res: print(ans) if __name__ == "__main__": main()