結果
| 問題 | 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 |
ソースコード
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()