結果

問題 No.1833 Subway Planning
ユーザー lam6er
提出日時 2025-04-16 00:33:43
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,727 bytes
コンパイル時間 397 ms
コンパイル使用メモリ 82,836 KB
実行使用メモリ 656,260 KB
最終ジャッジ日時 2025-04-16 00:35:29
合計ジャッジ時間 9,491 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 3 WA * 2 MLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque, defaultdict

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    edges = []
    original_adj = defaultdict(list)
    max_C = 0
    for _ in range(N-1):
        a = int(input[idx])
        b = int(input[idx+1])
        c = int(input[idx+2])
        idx +=3
        edges.append((a, b, c))
        original_adj[a].append((b, c))
        original_adj[b].append((a, c))
        if c > max_C:
            max_C = c

    def is_possible(K):
        S = [(a, b, c) for a, b, c in edges if c > K]
        if not S:
            return True
        adj = defaultdict(list)
        nodes = set()
        for a, b, c in S:
            adj[a].append(b)
            adj[b].append(a)
            nodes.add(a)
            nodes.add(b)
        degrees = defaultdict(int)
        for a in adj:
            degrees[a] = len(adj[a])
        for a in degrees.values():
            if a > 2:
                return False
        endpoints = [a for a in degrees if degrees[a] == 1]
        if len(endpoints) != 2:
            return False
        start = endpoints[0]
        visited = set()
        queue = deque([start])
        visited.add(start)
        while queue:
            u = queue.popleft()
            for v in adj[u]:
                if v not in visited:
                    visited.add(v)
                    queue.append(v)
        for node in nodes:
            if node not in visited:
                return False
        start_node, end_node = endpoints
        parent = {}
        min_c = {}
        parent[start_node] = None
        min_c[start_node] = float('inf')
        queue = deque([start_node])
        found = False
        final_min = None
        while queue and not found:
            u = queue.popleft()
            for (v, c) in original_adj[u]:
                if v == parent.get(u, None):
                    continue
                current_min = min(min_c[u], c) if u in min_c else c
                if v == end_node:
                    final_min = current_min
                    found = True
                    break
                if v not in parent:
                    parent[v] = u
                    min_c[v] = current_min
                    queue.append(v)
            if found:
                break
        if not found:
            return False
        m_min = max(c - K for a, b, c in S)
        return final_min >= m_min

    low = 0
    high = max_C
    answer = max_C
    while low <= high:
        mid = (low + high) // 2
        if is_possible(mid):
            answer = mid
            high = mid - 1
        else:
            low = mid + 1
    print(answer)

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