結果

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

ソースコード

diff # 

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