結果

問題 No.1393 Median of Walk
ユーザー lam6er
提出日時 2025-04-09 21:02:11
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,471 bytes
コンパイル時間 190 ms
コンパイル使用メモリ 83,032 KB
実行使用メモリ 78,608 KB
最終ジャッジ日時 2025-04-09 21:03:56
合計ジャッジ時間 6,149 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 1 -- * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    M = int(input[idx])
    idx += 1
    edges = []
    for _ in range(M):
        u = int(input[idx]) - 1
        idx += 1
        v = int(input[idx]) - 1
        idx += 1
        w = int(input[idx])
        idx += 1
        edges.append((u, v, w))

    reachable = [False] * N
    reachable[0] = True
    adj = [[] for _ in range(N)]
    for u, v, w in edges:
        adj[u].append(v)
    q = deque([0])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if not reachable[v]:
                reachable[v] = True
                q.append(v)

    def is_feasible(x):
        best_even = [-float('inf')] * N
        best_odd = [-float('inf')] * N
        best_even[0] = 0
        for _ in range(N - 1):
            updated = False
            for u, v, w in edges:
                c = 1 if w <= x else -1
                if best_even[u] != -float('inf'):
                    new_balance = best_even[u] + c
                    if new_balance > best_odd[v]:
                        best_odd[v] = new_balance
                        updated = True
                if best_odd[u] != -float('inf'):
                    new_balance = best_odd[u] + c
                    if new_balance > best_even[v]:
                        best_even[v] = new_balance
                        updated = True
            if not updated:
                break
        has_infinite = [False] * N
        for u, v, w in edges:
            c = 1 if w <= x else -1
            if best_even[u] != -float('inf'):
                new_balance = best_even[u] + c
                if new_balance > best_odd[v] and not has_infinite[v]:
                    has_infinite[v] = True
            if best_odd[u] != -float('inf'):
                new_balance = best_odd[u] + c
                if new_balance > best_even[v] and not has_infinite[v]:
                    has_infinite[v] = True

        q_infinite = deque()
        for i in range(N):
            if has_infinite[i]:
                q_infinite.append(i)
        while q_infinite:
            u = q_infinite.popleft()
            for v in adj[u]:
                if not has_infinite[v] and reachable[v]:
                    has_infinite[v] = True
                    q_infinite.append(v)

        res = [False] * N
        for i in range(N):
            if not reachable[i]:
                res[i] = False
            else:
                if (best_even[i] >= 0) or (best_odd[i] >= 1) or has_infinite[i]:
                    res[i] = True
                else:
                    res[i] = False
        return res

    sorted_ws = sorted(list(set(w for _, _, w in edges)))
    sorted_ws.append(0)
    sorted_ws.append(10**18)
    sorted_ws = sorted(sorted_ws)

    answers = [-1] * N
    for i in range(1, N):
        if not reachable[i]:
            answers[i] = -1
        else:
            left = 0
            right = len(sorted_ws) - 1
            best = -1
            while left <= right:
                mid = (left + right) // 2
                x = sorted_ws[mid]
                feasible = is_feasible(x)
                if feasible[i]:
                    best = x
                    right = mid - 1
                else:
                    left = mid + 1
            answers[i] = best

    for i in range(1, N):
        print(answers[i])

if __name__ == '__main__':
    main()
0