結果

問題 No.1393 Median of Walk
ユーザー gew1fw
提出日時 2025-06-12 15:40:53
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,083 bytes
コンパイル時間 352 ms
コンパイル使用メモリ 82,688 KB
実行使用メモリ 267,520 KB
最終ジャッジ日時 2025-06-12 15:41:01
合計ジャッジ時間 6,898 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 2 -- * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1

    adj = [[] for _ in range(N + 1)]
    all_weights = []

    for _ in range(M):
        u = int(input[ptr])
        ptr += 1
        v = int(input[ptr])
        ptr += 1
        w = int(input[ptr])
        ptr += 1
        adj[u].append((v, w))
        all_weights.append(w)

    if not all_weights:
        sorted_weights = []
    else:
        sorted_weights = sorted(list(set(all_weights)))

    def check(w, target_node):
        max_k = 2000  # Increased to handle longer paths
        max_c = [{} for _ in range(N + 1)]
        max_c[1][0] = 0
        queue = deque()
        queue.append((1, 0))

        while queue:
            u, k = queue.popleft()
            if k > max_k:
                continue
            current_c = max_c[u].get(k, -1)
            if current_c == -1:
                continue
            for edge in adj[u]:
                v, w_e = edge
                new_k = k + 1
                if new_k > max_k:
                    continue
                added_c = 1 if w_e <= w else 0
                new_c = current_c + added_c
                if new_k not in max_c[v] or new_c > max_c[v].get(new_k, -1):
                    max_c[v][new_k] = new_c
                    queue.append((v, new_k))

        if target_node > N:
            return False
        target_max_c = max_c[target_node]
        for k in target_max_c:
            if target_max_c[k] >= (k + 1) // 2:
                return True
        return False

    for i in range(2, N + 1):
        left = 0
        right = len(sorted_weights) - 1
        answer = -1
        while left <= right:
            mid = (left + right) // 2
            current_w = sorted_weights[mid]
            if check(current_w, i):
                answer = current_w
                right = mid - 1
            else:
                left = mid + 1
        print(answer if answer != -1 else -1)

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