/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 16ms 3.355 MiB
#2 Wrong Answer 17ms 3.441 MiB
#3 Wrong Answer 18ms 3.359 MiB

Code

def max_nodes_visited(N, K, edges):
    from collections import defaultdict
    
    # Create an adjacency list for the tree
    tree = defaultdict(list)
    for u, v in edges:
        tree[u].append(v)
        tree[v].append(u)
    
    visited = set()  # To track unique nodes visited
    revisit_count = 0  # To count how many nodes are revisited

    def dfs(node, parent):
        nonlocal revisit_count
        visited.add(node)

        for neighbor in tree[node]:
            if neighbor == parent:
                continue  # Skip the parent node
            
            if neighbor in visited:
                # We have already visited this node
                if revisit_count < K:
                    # If we can revisit
                    revisit_count += 1
                    dfs(neighbor, node)  # Continue DFS
            else:
                # If not visited, we visit it normally
                dfs(neighbor, node)
    
    # Start DFS from node 1, which has no parent (use 0 or None)
    dfs(1, -1)

    # The total unique nodes visited is the size of the visited set
    return len(visited)

# Input reading
if __name__ == "__main__":
    import sys
    input = sys.stdin.read
    data = input().splitlines()
    
    # Read first line
    first_line = data[0].split()
    N = int(first_line[0])
    K = int(first_line[1])
    
    edges = []
    for i in range(1, N):
        u, v = map(int, data[i].split())
        edges.append((u, v))
    
    # Calculate the maximum nodes Thakur can visit
    result = max_nodes_visited(N, K, edges)
    print(result)

Information

Submit By
Type
Submission
Problem
P1111 Thakurs tree game
Contest
Brain Booster #7
Language
Python 3 (Python 3.12.3)
Submit At
2024-11-05 15:21:34
Judged At
2024-11-05 15:21:34
Judged By
Score
0
Total Time
18ms
Peak Memory
3.441 MiB