結果

問題 No.1600 Many Shortest Path Problems
ユーザー qwewe
提出日時 2025-05-14 13:08:15
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 15,099 bytes
コンパイル時間 480 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 852,704 KB
最終ジャッジ日時 2025-05-14 13:10:00
合計ジャッジ時間 6,622 ms
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample -- * 3
other AC * 4 MLE * 1 -- * 46
権限があれば一括ダウンロードができます

ソースコード

diff #

import sys

# Increase recursion depth limit for deep structures like MST potentially
# Needs to be large enough for N=200000. Python default is often 1000.
# Set it to slightly more than max N + M maybe, though N vertices dominate depth.
sys.setrecursionlimit(200000 + 50) 

def solve():
    N, M = map(int, sys.stdin.readline().split())

    # Store edge information. We'll need edge index (1-based) and its endpoints.
    edges_info = [] # Stores dict for each edge: u, v, id
    # Map edge ID (1-based) to its information dict for quick lookup later
    edge_map_by_id = {} 

    for i in range(M):
        u, v = map(int, sys.stdin.readline().split())
        # Store edge data. Weight 2^id calculation will be done on the fly when needed.
        edge_data = { 'u': u, 'v': v, 'id': i + 1} 
        edges_info.append(edge_data)
        edge_map_by_id[i + 1] = edge_data

    # --- Kruskal's Algorithm to build Minimum Spanning Tree (MST) ---
    # Use Disjoint Set Union (DSU) data structure.
    parent_dsu = list(range(N + 1))
    def find_set(v):
        # Path compression heuristic
        if v == parent_dsu[v]:
            return v
        parent_dsu[v] = find_set(parent_dsu[v])
        return parent_dsu[v]

    def unite_sets(a, b):
        a = find_set(a)
        b = find_set(b)
        if a != b:
            # Basic union (no rank/size optimization, usually sufficient)
            parent_dsu[b] = a
            return True
        return False

    # Build MST adjacency list and identify non-MST edges
    mst_adj = [[] for _ in range(N + 1)] # Use list for adjacency list: node -> list of {'to': neighbor, 'id': edge_id}
    non_mst_edges_idx = [] # List of 0-based indices of edges NOT in MST
    mst_edge_ids = set() # Store IDs of edges that are part of the MST for quick check

    # Edges are implicitly sorted by index 1 to M, which corresponds to weights 2^1 to 2^M
    for i in range(M):
        edge_data = edges_info[i]
        u, v = edge_data['u'], edge_data['v']
        
        if unite_sets(u, v):
            # Edge is part of MST
            mst_edge_ids.add(edge_data['id'])
            # Add edge to MST adjacency list for both endpoints
            mst_adj[u].append({'to': v, 'id': edge_data['id']})
            mst_adj[v].append({'to': u, 'id': edge_data['id']})
        else:
            # Edge creates a cycle, not part of MST
            non_mst_edges_idx.append(i) 

    # --- Precomputation for path queries on MST using Binary Lifting ---
    MAX_LOG_N = (N).bit_length() # Maximum power of 2 needed for binary lifting, depends on N
    
    # Binary lifting tables
    # parent_binlift[node][k] = (ancestor_at_2^k_distance, edge_id_to_parent_at_2^0)
    # Note: edge_id is only stored for k=0 (direct parent)
    parent_binlift = [[(0, 0)] * MAX_LOG_N for _ in range(N + 1)] 
    depth = [-1] * (N + 1) # Store depth of each node from root
    # path_xor_sum_binlift[node][k] stores the XOR sum of 2^edge_id for edges on the path from node to its 2^k ancestor
    path_xor_sum_binlift = [[0] * MAX_LOG_N for _ in range(N + 1)] # Python's arbitrary precision integers handle large XOR sums

    
    # Use BFS to initialize level 0 of binary lifting tables and depths
    # Assume graph is connected and vertex 1 exists. Root the MST at vertex 1.
    q = [(1, 0, 0)] # Queue stores (current_node, parent_node, depth)
    depth[1] = 0
    
    head = 0
    # processed_nodes_order = [] # Not strictly needed, can build tables directly in BFS/DFS

    while head < len(q):
        curr, p, d = q[head]
        head += 1
        # processed_nodes_order.append(curr) # Optional: for ordered processing later
               
        # Iterate through neighbors in MST adjacency list
        for edge in mst_adj[curr]:
            neighbor = edge['to']
            edge_id = edge['id']
            if neighbor != p: # Avoid going back to parent
                # If neighbor hasn't been visited yet
                if depth[neighbor] == -1: 
                    depth[neighbor] = d + 1
                    # Set direct parent (k=0 level)
                    parent_binlift[neighbor][0] = (curr, edge_id)
                    # Set path XOR sum for edge to direct parent
                    # The weight is 2^edge_id. In Python, left shift `1 << k` computes 2^k.
                    path_xor_sum_binlift[neighbor][0] = (1 << edge_id)
                    q.append((neighbor, curr, d + 1))

    # Compute full binary lifting tables (levels 1 to MAX_LOG_N-1)
    for i in range(1, MAX_LOG_N):
        for node in range(1, N + 1):
             # Get the 2^(i-1) ancestor
             p_node, _ = parent_binlift[node][i-1]
             if p_node != 0: # If the ancestor exists
                # Get the 2^(i-1) ancestor of the ancestor (which is the 2^i ancestor)
                pp_node, _ = parent_binlift[p_node][i-1]
                if pp_node != 0: # If the 2^i ancestor exists
                    # Store the 2^i ancestor. Edge ID is irrelevant here.
                    parent_binlift[node][i] = (pp_node, 0) 
                    # Compute path XOR sum using values from level i-1
                    path_xor_sum_binlift[node][i] = path_xor_sum_binlift[node][i-1] ^ path_xor_sum_binlift[p_node][i-1]

    # --- Helper functions for LCA and path XOR sum ---
    
    # Find Lowest Common Ancestor (LCA) of two nodes u, v
    def get_lca(u, v):
        # Ensure u is the deeper node
        if depth[u] < depth[v]: u, v = v, u
        
        # Lift node u up to the same depth as v
        for i in range(MAX_LOG_N - 1, -1, -1):
            # If 2^i step doesn't go above v's depth
            if depth[u] - (1 << i) >= depth[v]:
                u = parent_binlift[u][i][0]
        
        # If u and v are now the same node, it's the LCA
        if u == v: return u

        # Lift u and v simultaneously until their parents are the same
        for i in range(MAX_LOG_N - 1, -1, -1):
             p_u, _ = parent_binlift[u][i]
             p_v, _ = parent_binlift[v][i]
             # Check if parents exist and are different
             if p_u != p_v:
                u = p_u
                v = p_v
        
        # The LCA is the direct parent of the current u (or v)
        return parent_binlift[u][0][0]


    # Calculate XOR sum of 2^edge_id for path from node u up to target_ancestor
    def get_path_xor_sum(u, target_ancestor):
        res = 0
        target_depth = depth[target_ancestor]
        
        # Lift u step-by-step using binary lifting powers
        for i in range(MAX_LOG_N - 1, -1, -1):
             # If taking a 2^i step doesn't go above the target ancestor's depth
             if depth[u] - (1 << i) >= target_depth:
                # XOR the path sum for this segment
                res ^= path_xor_sum_binlift[u][i]
                # Move u up
                u = parent_binlift[u][i][0]
        return res


    # --- Precompute Cycle Information for Non-MST Edges ---
    # V_k stores the XOR sum L(C_k) for the cycle C_k formed by non-MST edge k
    # L(C_k) = 2^k XOR L(P''_{MST,k}), where P''_{MST,k} is the path in MST between endpoints of edge k.
    V_k = {} # Map: 0-based index k_idx -> BigInt value V_k
    for k_idx in non_mst_edges_idx:
        edge_data = edges_info[k_idx]
        p, q = edge_data['u'], edge_data['v']
        edge_id = edge_data['id'] # 1-based ID
        
        lca = get_lca(p, q)
        # Calculate XOR sum of MST path between p and q
        path_xor = get_path_xor_sum(p, lca) ^ get_path_xor_sum(q, lca)
        # Calculate V_k value using the cycle property
        V_k[k_idx] = (1 << edge_id) ^ path_xor

    
    # --- Precompute DFS start/end times for subtree checks ---
    # Needed to efficiently check if an edge is on a path between two nodes
    timer = 0
    tin = [-1] * (N + 1) # Stores entry time of DFS
    tout = [-1] * (N + 1) # Stores exit time of DFS
    
    # Use iterative DFS to avoid deep recursion issues
    dfs_stack = [(1, 0, 'enter')] # Stack stores (node, parent, state) state='enter' or 'exit'
    
    while dfs_stack:
         u, p, state = dfs_stack.pop()
         
         if state == 'enter':
             timer += 1
             tin[u] = timer
             dfs_stack.append((u, p, 'exit')) # Schedule exit processing for this node

             # Explore neighbors in MST
             for edge in mst_adj[u]:
                 neighbor = edge['to']
                 if neighbor != p:
                     # Push neighbor onto stack for processing
                    dfs_stack.append((neighbor, u, 'enter'))
         
         elif state == 'exit':
             # Process node upon exiting its subtree
             timer += 1
             tout[u] = timer

    # Check if node u is an ancestor of node v using DFS times
    def is_ancestor(u, v): 
       # Handle cases where nodes might not have been visited (e.g. disconnected graph, though problem says connected)
       if tin[u] == -1 or tin[v] == -1: return False
       # Standard check using entry and exit times
       return tin[u] <= tin[v] and tout[u] >= tout[v]

    
    # --- Precompute powers of 2 modulo MOD ---
    MOD = 10**9 + 7
    P2 = [1] * (M + 1) # P2[i] stores 2^i mod MOD
    for i in range(1, M + 1): P2[i] = (P2[i-1] * 2) % MOD

    # Function to calculate the final path sum modulo MOD from its XOR sum representation
    def get_mod_sum(xor_val):
        res = 0
        # Iterate through bits potentially up to M. Max possible edge ID is M. Weight is 2^M.
        # Need to check bits up to M.
        # A path sum can exceed 2^M, but individual weights are 2^i for i<=M.
        # Determine appropriate bit length, M+1 is safe. Or dynamically check xor_val.bit_length().
        max_bits = M + 1 
        if xor_val > 0:
            max_bits = xor_val.bit_length()
            
        for i in range(max_bits):
            # If the i-th bit is set in the XOR sum
            if (xor_val >> i) & 1:
                # Add the corresponding power of 2 (mod MOD)
                # Check if index i is valid (<= M)
                if i <= M: 
                  res = (res + P2[i]) % MOD
        return res

    # --- Process Queries ---
    Q = int(sys.stdin.readline())
    results = [] # Store results for each query

    for _ in range(Q):
        x, y, z_id = map(int, sys.stdin.readline().split())
        
        # Find LCA of query nodes x, y
        lca_xy = get_lca(x, y)
        # Calculate XOR sum of the MST path between x and y
        current_path_xor_sum = get_path_xor_sum(x, lca_xy) ^ get_path_xor_sum(y, lca_xy)
        
        # Check if the forbidden edge z_id is on the MST path between x and y
        is_z_on_path = False
        if z_id in mst_edge_ids: # Check if z_id is even part of the MST
             # Determine which endpoint is child (u) and which is parent (v) for edge z_id
             z_edge_info = edge_map_by_id[z_id]
             zu, zv = z_edge_info['u'], z_edge_info['v']
             
             u_for_z, v_for_z = -1, -1 # u: child, v: parent
             # Check depth to identify parent-child relationship
             if depth[zu] > depth[zv]: u_for_z, v_for_z = zu, zv
             elif depth[zv] > depth[zu]: u_for_z, v_for_z = zv, zu

             # Verify this edge is indeed the one connecting u_for_z and v_for_z in MST
             if u_for_z != -1 and parent_binlift[u_for_z][0] == (v_for_z, z_id): 
                # Check if z_id lies on the path x <-> y using LCA and subtree properties
                 if is_ancestor(lca_xy, v_for_z): # LCA of x,y must be ancestor of parent endpoint v
                      # Check if x and y are separated by the edge z_id
                      is_x_in_subtree = is_ancestor(u_for_z, x) # Is x in subtree of child u?
                      is_y_in_subtree = is_ancestor(u_for_z, y) # Is y in subtree of child u?
                      # If one is in subtree and the other is not, the path must cross edge z_id
                      if is_x_in_subtree != is_y_in_subtree:
                           is_z_on_path = True
        
        # Case 1: Forbidden edge z_id is NOT on the shortest (MST) path
        if not is_z_on_path:
            # The MST path is valid and the shortest. Output its length mod MOD.
            results.append(get_mod_sum(current_path_xor_sum))
        # Case 2: Forbidden edge z_id IS on the shortest (MST) path
        else:
            # Need to find the shortest alternative path.
            # Iterate through all non-MST edges to find potential alternative paths.
            min_alt_path_xor_sum = float('inf') # Use infinity for minimum tracking
            found_alt = False # Flag if any alternative path is found
            
            # Re-identify u_for_z based on depth for subtree check below
            # This is needed because it was inside the `if z_id in mst_edge_ids` block
            z_edge_info = edge_map_by_id[z_id]
            zu, zv = z_edge_info['u'], z_edge_info['v']
            u_for_z = -1
            if depth[zu] > depth[zv]: u_for_z = zu
            elif depth[zv] > depth[zu]: u_for_z = zv
            # If u_for_z remains -1, something is wrong (e.g., endpoints at same depth? Only if root edge?)

            for k_idx in non_mst_edges_idx: 
                 # Check if V_k value exists for this index k_idx
                 if k_idx not in V_k: continue

                 # Get endpoints p, q of the non-MST edge k
                 p, q = edges_info[k_idx]['u'], edges_info[k_idx]['v']
                 
                 # Check if cycle C_k (formed by edge k and MST path p<->q) contains the forbidden edge z_id
                 # This happens if p and q are separated by edge z_id
                 # i.e., one of p,q is in the subtree of u_for_z (child endpoint of z_id), and the other is not.
                 if u_for_z == -1: continue # Skip if child endpoint identification failed

                 is_p_in_subtree = is_ancestor(u_for_z, p)
                 is_q_in_subtree = is_ancestor(u_for_z, q)

                 # If endpoints p,q are separated by edge z_id
                 if is_p_in_subtree != is_q_in_subtree:
                      # Calculate the XOR sum of the alternative path P' = P_MST XOR C_k
                      alt_path_xor_sum = current_path_xor_sum ^ V_k[k_idx]
                      # Update minimum alternative path length found so far
                      if alt_path_xor_sum < min_alt_path_xor_sum:
                          min_alt_path_xor_sum = alt_path_xor_sum
                      found_alt = True # Mark that at least one alternative path exists

            # After checking all non-MST edges:
            if not found_alt:
                 # If no alternative path was found, it means removing z_id disconnects x and y.
                 results.append("-1") 
            else:
                 # Output the length of the shortest alternative path found, modulo MOD.
                 results.append(get_mod_sum(min_alt_path_xor_sum))

    # Print all computed results for the queries
    sys.stdout.write('\n'.join(map(str, results)) + '\n')

solve()
0