結果
| 問題 |
No.1393 Median of Walk
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:24:59 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,903 bytes |
| コンパイル時間 | 168 ms |
| コンパイル使用メモリ | 82,636 KB |
| 実行使用メモリ | 87,508 KB |
| 最終ジャッジ日時 | 2025-05-14 13:26:04 |
| 合計ジャッジ時間 | 4,357 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 5 TLE * 1 -- * 33 |
ソースコード
import sys
def solve():
N, M = map(int, sys.stdin.readline().split())
edges = []
all_weights_set = set()
for _ in range(M):
u, v, w = map(int, sys.stdin.readline().split())
edges.append((u - 1, v - 1, w)) # 0-indexed nodes
all_weights_set.add(w)
# If no edges, all answers are -1, unless N=1 (not possible by constraints)
if not all_weights_set and N > 1:
for _ in range(N - 1):
print("-1")
return
# If N=1 (problem says N>=2), no output.
# If N > 1 and M=0, all are -1.
if M == 0 and N > 1:
for _ in range(N - 1):
print("-1")
return
sorted_unique_weights = sorted(list(all_weights_set))
U = len(sorted_unique_weights)
# Bellman-Ford DP states: dp[node_idx][parity]
# parity 0 for even length, 1 for odd length.
# Initialize distances to a value representing infinity.
# Max path sum for simple paths is N-1, min is -(N-1).
# If N iterations are run, values can go lower due to negative cycles.
# P_INF must be larger than any possible finite sum. N+1 is fine if costs are +/-1.
# Using N+5 for safety margin.
P_INF = N + 5
# Stores final answer for each target node (index 0 to N-2 for nodes 2 to N)
ans_values = [-1] * (N - 1)
# Stores index in sorted_unique_weights for current best answer for node_idx
ans_indices = [-1] * N
# Stores [low_idx, high_idx] for binary search for each target node
# Target nodes are 1 to N-1 (for actual graph nodes 2 to N)
# Using original 0-indexed node indices from input.
# Target node indices here are 0-indexed graph node indices.
nodes_search_ranges = {}
for i in range(1, N): # Target nodes 1 through N-1 (0-indexed)
nodes_search_ranges[i] = [0, U - 1]
# Parallel binary search: approx log U iterations
# Max U is M (2500). log2(2500) ~ 11.3. So around 12-14 iterations.
for _iteration_count in range(U.bit_length() + 2): # Sufficient iterations for BS
mid_idx_to_targets_map = {} # Map: mid_weight_idx -> list of target_node_indices
active_searches_exist = False
for target_node_idx_0_indexed in range(1, N):
# Ensure this target_node_idx is still being processed
if target_node_idx_0_indexed not in nodes_search_ranges:
continue # Should not happen with this structure
low_W_idx, high_W_idx = nodes_search_ranges[target_node_idx_0_indexed]
if low_W_idx <= high_W_idx:
active_searches_exist = True
mid_W_idx = low_W_idx + (high_W_idx - low_W_idx) // 2
if mid_W_idx not in mid_idx_to_targets_map:
mid_idx_to_targets_map[mid_W_idx] = []
mid_idx_to_targets_map[mid_W_idx].append(target_node_idx_0_indexed)
if not active_searches_exist: # All binary searches concluded
break
# For each distinct median value X to test this iteration
for mid_W_idx, current_targets_for_this_X in mid_idx_to_targets_map.items():
X_median_candidate = sorted_unique_weights[mid_W_idx]
# Run Bellman-Ford for this X_median_candidate
dp = [[P_INF] * 2 for _ in range(N)]
dp[0][0] = 0 # Cost to reach node 0 (vertex 1) with even (0) length path is 0
for _bf_iter in range(N): # N iterations for Bellman-Ford
for u, v, w_original in edges:
cost = 1 if w_original > X_median_candidate else -1
# Path from u (even len) to v (odd len)
if dp[u][0] != P_INF:
new_cost_v_odd = dp[u][0] + cost
if new_cost_v_odd < dp[v][1]:
# Clamp to prevent overly negative values if not using float('inf')
dp[v][1] = max(new_cost_v_odd, -(N + 1))
# Path from u (odd len) to v (even len)
if dp[u][1] != P_INF:
new_cost_v_even = dp[u][1] + cost
if new_cost_v_even < dp[v][0]:
dp[v][0] = max(new_cost_v_even, -(N + 1))
# For each target node that was testing this X_median_candidate
for target_node_idx_0_indexed in current_targets_for_this_X:
# Check condition
path_found_odd_len = (dp[target_node_idx_0_indexed][1] != P_INF and \
dp[target_node_idx_0_indexed][1] <= -1)
path_found_even_len = (dp[target_node_idx_0_indexed][0] != P_INF and \
dp[target_node_idx_0_indexed][0] <= 0)
check_result = path_found_odd_len or path_found_even_len
# Update binary search range for this target_node_idx
if check_result: # X_median_candidate is a possible median (or something smaller)
ans_indices[target_node_idx_0_indexed] = mid_W_idx
nodes_search_ranges[target_node_idx_0_indexed][1] = mid_W_idx - 1 # Try smaller
else: # X_median_candidate is too small, need larger median
nodes_search_ranges[target_node_idx_0_indexed][0] = mid_W_idx + 1 # Try larger
# Populate final answers from stored indices
for i in range(1, N): # For target nodes 1 to N-1 (0-indexed)
if ans_indices[i] != -1:
# ans_values is 0-indexed for N-1 elements (targets 2 to N)
# So target node i (0-indexed) corresponds to ans_values[i-1]
ans_values[i-1] = sorted_unique_weights[ans_indices[i]]
# else it remains -1 (default)
for val in ans_values:
print(val)
solve()