Submission #881433

#	Time	Username	Problem	Language	Result	Execution time	Memory
881433		CBNK30_theviet	Parkovi (COCI22_parkovi)	Cpython 3	0 / 110	724 ms	81480 KiB

Main

import sys
from collections import defaultdict

def solve():
    n, k = map(int, input().split())
    graph = defaultdict(list)

    for _ in range(n - 1):
        a, b, w = map(int, input().split())
        graph[a].append((b, w))
        graph[b].append((a, w))

    def is_feasible(mid):
        nonlocal k
        nonlocal graph

        def dfs(node, parent, mid):
            nonlocal count
            nonlocal k
            nonlocal graph

            if count >= k:
                return

            for neighbor, weight in graph[node]:
                if neighbor != parent:
                    if weight > mid:
                        count += 1
                    dfs(neighbor, node, mid)

        count = 0
        dfs(1, -1, mid)

        return count <= k

    left, right = 0, 1e18

    while abs(right - left) > 1e-7:
        mid = (left + right) / 2
        if is_feasible(mid):
            right = mid
        else:
            left = mid

    print("{:.7f}".format(right))

    def build_parks(node, parent, mid):
        nonlocal count
        nonlocal k
        nonlocal graph

        if count >= k:
            return

        for neighbor, weight in graph[node]:
            if neighbor != parent:
                if weight > mid:
                    count += 1
                build_parks(neighbor, node, mid)

    count = 0
    build_parks(1, -1, right)

    parks = [i for i in range(1, n + 1) if i <= k]
    print(" ".join(map(str, parks)))

if __name__ == "__main__":
    solve()

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60