/ SeriousOJ /

Record Detail

Compile Error

/w/foo.js:1
import sys
^^^^^^

SyntaxError: Cannot use import statement outside a module
    at internalCompileFunction (node:internal/vm:73:18)
    at wrapSafe (node:internal/modules/cjs/loader:1274:20)
    at node:internal/main/check_syntax:84:41
    at loadESM (node:internal/process/esm_loader:34:13)
    at checkSyntax (node:internal/main/check_syntax:84:21)

Node.js v18.19.1

Code

import sys
input = sys.stdin.read
from collections import defaultdict, deque

def max_nodes_visited(N, K, edges):
    # Building the tree
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    # Step 1: Calculate subtree sizes and depths using DFS
    subtree_size = [0] * (N + 1)
    depth = [0] * (N + 1)
    visited = [False] * (N + 1)

    def dfs(node, d):
        visited[node] = True
        depth[node] = d
        subtree_size[node] = 1
        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs(neighbor, d + 1)
                subtree_size[node] += subtree_size[neighbor]
    
    dfs(1, 0)

    # Step 2: Calculate potential revisits sorted by subtree size
    nodes_by_subtree = sorted(range(1, N + 1), key=lambda x: -subtree_size[x])
    
    # Step 3: Simulate revisiting up to K nodes to maximize coverage
    total_visited = 0
    revisited = 0
    visited_nodes = set()

    for node in nodes_by_subtree:
        if revisited < K:
            total_visited += subtree_size[node]
            revisited += 1
        else:
            break

    # Ensure the total nodes counted doesn't exceed N
    total_visited = min(total_visited, N)
    return total_visited

# Example usage:
data = input().split()
index = 0
T = int(data[index])
index += 1
results = []
for _ in range(T):
    N, K = int(data[index]), int(data[index + 1])
    index += 2
    edges = []
    for __ in range(N - 1):
        u, v = int(data[index]), int(data[index + 1])
        edges.append((u, v))
        index += 2
    results.append(str(max_nodes_visited(N, K, edges)))

# Output all results
print("\n".join(results))

Information

Submit By
Type
Submission
Problem
P1111 Thakurs tree game
Contest
Brain Booster #7
Language
JavaScript (Node.js v18.19.1)
Submit At
2024-11-05 15:09:46
Judged At
2024-11-11 02:31:21
Judged By
Score
0
Total Time
0ms
Peak Memory
0 Bytes