結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

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