結果

問題 No.1523 +/- Tree
ユーザー gew1fw
提出日時 2025-06-12 21:11:59
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,380 bytes
コンパイル時間 474 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 67,968 KB
最終ジャッジ日時 2025-06-12 21:14:11
合計ジャッジ時間 9,188 ms
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 17 WA * 27
権限があれば一括ダウンロードができます

ソースコード

diff #

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    K = int(input[idx])
    idx += 1

    if K == 1 or K >= N - 1:
        print("No")
        return

    if K == 2:
        if N < 4:
            print("No")
            return
        edges = []
        # Main chain 1-2-3-4 with edges 2, -3, 2
        edges.append((1, 2, 2))
        edges.append((2, 3, -3))
        edges.append((3, 4, 2))
        # Remaining nodes are connected to 1 with weight 2
        for i in range(5, N+1):
            edges.append((1, i, 2))
        # Check sum
        total = 2 -3 +2 + 2*(N -4)
        if total <= 0:
            print("No")
            return
        print("Yes")
        for u, v, w in edges:
            print(u, v, w)
        return

    # For K >=3
    M = N - (K+1)
    if M * 2 <= K:
        print("No")
        return

    edges = []
    # Main chain: K edges, all -1
    for i in range(1, K+1):
        u = i
        v = i + 1
        edges.append((u, v, -1))
    # Remaining M nodes connected to 1
    for i in range(K+2, N+1):
        edges.append((1, i, 2))
    # Check sum
    sum_main = -K
    sum_leaves = 2 * M
    total = sum_main + sum_leaves
    if total <= 0:
        print("No")
        return
    print("Yes")
    for u, v, w in edges:
        print(u, v, w)

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