結果

問題 No.3057 Tree Distance Set
ユーザー LyricalMaestro
提出日時 2025-03-15 16:14:43
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 59 ms / 2,000 ms
コード長 2,046 bytes
コンパイル時間 468 ms
コンパイル使用メモリ 82,008 KB
実行使用メモリ 71,256 KB
最終ジャッジ日時 2025-03-15 16:14:46
合計ジャッジ時間 2,920 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/3057

from collections import deque

def main():
    K = int(input())
    D = list(map(int, input().split()))

    D.sort()

    S = []
    T = []
    edges = []
    # 1つめ
    d = D[0]
    S.append(0)
    T.append(0)
    for i in range(d):
        edges.append((i, i + 1))
    S.append(d)
    T.append(d)
    target = d - (d // 2)
    d0 = d // 2
    total_index = d
    for j in range(1, K):
        d = D[j]
        d1 = d - d0
        v = target
        T.append(v)
        for i in range(d1):
            edges.append((v, total_index + 1 + i))
            v = total_index + 1 + i
        S.append(v)
        T.append(v)
        total_index += d1
        target = total_index - d // 2
        d0 = d // 2

    # 木を構築
    next_nodes = [[] for _ in range(total_index + 1)]
    for i in range(len(edges)):
        u, v = edges[i]
        next_nodes[u].append((v, i))
        next_nodes[v].append((u, i))

    passed_edges = set()
    queue = deque()
    t_set = set(T)
    for t in T:
        queue.append(t)
    new_edges = []
    while len(queue) > 0:
        t = queue.popleft()
        for u, index in next_nodes[t]:
            if index in passed_edges:
                continue

            array = 1
            passed_edges.add(index)
            while u not in t_set:
                for v, n_index in next_nodes[u]:
                    if n_index not in passed_edges:
                        array += 1
                        passed_edges.add(n_index)
                        u = v
                        break
            new_edges.append((t, u, array))

    T.sort()
    t_map = {}
    for i, t in enumerate(T):
        t_map[t] = i + 1

    answer_edges = []
    for u, v, w in new_edges:
        answer_edges.append((t_map[u], t_map[v], w))
    
    # 答え出力
    print(len(T))
    for u, v, w in answer_edges:
        print(u, v, w)
    print(len(S))
    print(" ".join(map(lambda x : str(t_map[x]) , S)))














                


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