oj.uz

Submission #881433

# Submission time Handle Problem Language Result Execution time Memory
881433 2023-12-01T08:48:03 Z CBNK30_theviet Parkovi (COCI22_parkovi) Python 3
0 / 110
 724 ms 81480 KB 
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.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 3420 KB Expected integer, but "0.0000001" found
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 663 ms 71584 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 724 ms 81480 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 3420 KB Expected integer, but "0.0000001" found
2 Halted 0 ms 0 KB -