結果

問題 No.1326 ふたりのDominator
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 15:22:44
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 5,723 bytes
コンパイル時間 384 ms
コンパイル使用メモリ 82,144 KB
実行使用メモリ 687,804 KB
最終ジャッジ日時 2025-06-12 15:22:49
合計ジャッジ時間 5,206 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 1 MLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0