結果

問題 No.1833 Subway Planning
ユーザー lam6er
提出日時 2025-03-31 17:43:48
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,272 bytes
コンパイル時間 264 ms
コンパイル使用メモリ 82,140 KB
実行使用メモリ 534,608 KB
最終ジャッジ日時 2025-03-31 17:44:42
合計ジャッジ時間 8,875 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 3 WA * 2 MLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict, deque

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

    max_M = max(c for a, b, c in edges)
    low = 0
    high = max_M
    ans = max_M

    while low <= high:
        mid = (low + high) // 2
        S_edges = [ (a, b, c) for a, b, c in edges if c > mid ]

        # Case 1: No edges in S_edges, feasible.
        if not S_edges:
            ans = mid
            high = mid -1
            continue

        # Build adjacency list and collect nodes
        nodes = set()
        adj = defaultdict(list)
        for a, b, c in S_edges:
            nodes.add(a)
            nodes.add(b)
            adj[a].append(b)
            adj[b].append(a)

        # Check connectivity
        start_node = next(iter(nodes))
        visited = set()
        visited.add(start_node)
        q = deque([start_node])
        while q:
            u = q.popleft()
            for v in adj[u]:
                if v not in visited:
                    visited.add(v)
                    q.append(v)

        if visited != nodes:
            low = mid +1
            continue

        # Check degrees <= 2
        degree = defaultdict(int)
        for a, b, c in S_edges:
            degree[a] += 1
            degree[b] += 1

        valid_degree = True
        for node in degree:
            if degree[node] > 2:
                valid_degree = False
                break
        if not valid_degree:
            low = mid +1
            continue

        # Check exactly two nodes with degree 1
        cnt_deg1 = 0
        for node in degree:
            if degree[node] ==1:
                cnt_deg1 +=1
        if cnt_deg1 !=2:
            low = mid +1
            continue

        # Check max_c - min_c <= mid
        max_c = max(c for a, b, c in S_edges)
        min_c = min(c for a, b, c in S_edges)
        if (max_c - min_c) > mid:
            low = mid +1
            continue

        # All conditions met
        ans = mid
        high = mid -1

    print(ans)

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