結果

問題 No.1833 Subway Planning
ユーザー gew1fw
提出日時 2025-06-12 20:55:46
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,724 bytes
コンパイル時間 273 ms
コンパイル使用メモリ 82,524 KB
実行使用メモリ 495,564 KB
最終ジャッジ日時 2025-06-12 20:59:27
合計ジャッジ時間 9,556 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 3 WA * 2 TLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque, defaultdict

def main():
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline())
    edges = []
    edges_dict = {}
    for _ in range(N-1):
        u, v, c = map(int, sys.stdin.readline().split())
        edges.append((u, v, c))
        edges_dict[(u, v)] = c
        edges_dict[(v, u)] = c

    max_initial = max(c for u, v, c in edges)
    low = 0
    high = max_initial

    def is_feasible(X):
        E = []
        nodes = set()
        for u, v, c in edges:
            if c > X:
                E.append((u, v, c))
                nodes.add(u)
                nodes.add(v)
        if not E:
            return True

        adj = defaultdict(list)
        for u, v, c in E:
            adj[u].append(v)
            adj[v].append(u)

        visited = set()
        start = next(iter(nodes)) if nodes else None
        if start is None:
            return True

        q = deque([start])
        visited.add(start)
        while q:
            u = q.popleft()
            for v in adj[u]:
                if v not in visited:
                    visited.add(v)
                    q.append(v)

        if len(visited) != len(nodes):
            return False

        degree = defaultdict(int)
        for u in adj:
            degree[u] = len(adj[u])

        deg1 = 0
        deg2 = 0
        for u in nodes:
            d = degree[u]
            if d > 2:
                return False
            if d == 1:
                deg1 += 1
            elif d == 2:
                deg2 += 1

        if deg1 != 2:
            return False

        ends = [u for u in nodes if degree[u] == 1]
        if len(ends) != 2:
            return False

        u, v = ends
        parent = {}
        c_list = []
        visited_bfs = set([u])
        q = deque([u])
        parent[u] = None

        while q:
            current = q.popleft()
            for neighbor in adj[current]:
                if neighbor not in visited_bfs:
                    visited_bfs.add(neighbor)
                    parent[neighbor] = current
                    c = edges_dict[(current, neighbor)]
                    c_list.append(c)
                    q.append(neighbor)

        if not c_list:
            max_c = E[0][2]
            min_c = E[0][2]
        else:
            max_c = max(c_list)
            min_c = min(c_list)

        if (max_c - min_c) <= X:
            return True
        else:
            return False

    answer = max_initial
    while low <= high:
        mid = (low + high) // 2
        if is_feasible(mid):
            answer = mid
            high = mid - 1
        else:
            low = mid + 1
    print(answer)

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