/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Wrong Answer 18ms 3.398 MiB
#2 Wrong Answer 18ms 3.367 MiB
#3 Wrong Answer 18ms 3.508 MiB
#4 Wrong Answer 27ms 4.57 MiB
#5 Wrong Answer 182ms 21.648 MiB
#6 Wrong Answer 320ms 35.422 MiB
#7 Wrong Answer 244ms 27.785 MiB
#8 Wrong Answer 147ms 14.938 MiB
#9 Wrong Answer 348ms 36.887 MiB
#10 Wrong Answer 386ms 41.695 MiB
#11 Wrong Answer 270ms 31.094 MiB
#12 Wrong Answer 318ms 34.953 MiB
#13 Wrong Answer 130ms 17.402 MiB
#14 Wrong Answer 417ms 45.898 MiB
#15 Wrong Answer 198ms 23.453 MiB
#16 Wrong Answer 101ms 15.781 MiB
#17 Wrong Answer 97ms 15.801 MiB
#18 Wrong Answer 97ms 15.789 MiB
#19 Wrong Answer 486ms 72.574 MiB
#20 Wrong Answer 491ms 72.582 MiB
#21 Wrong Answer 491ms 72.617 MiB
#22 Wrong Answer 564ms 93.828 MiB
#23 Wrong Answer 831ms 90.809 MiB
#24 Wrong Answer 819ms 90.723 MiB
#25 Wrong Answer 539ms 90.34 MiB
#26 Wrong Answer 43ms 7.684 MiB

Code

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

def bfs(start_node, graph, N):
    distances = [-1] * N
    distances[start_node] = 0
    queue = deque([start_node])
    
    max_dist = 0
    furthest_node = start_node
    
    while queue:
        node = queue.popleft()
        current_dist = distances[node]
        
        for neighbor in graph[node]:
            if distances[neighbor] == -1:
                distances[neighbor] = current_dist + 1
                queue.append(neighbor)
                if distances[neighbor] > max_dist:
                    max_dist = distances[neighbor]
                    furthest_node = neighbor
                    
    return furthest_node, max_dist

def minimum_seconds_to_collect_apples(T, test_cases):
    results = []
    
    for N, apple_nodes, edges in test_cases:
        if not any(apple_nodes):
            results.append("0")
            continue
        
        # Build the adjacency list for the tree
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        
        # Find any node with an apple
        start_node = next(i for i in range(N) if apple_nodes[i])
        
        # First BFS to find the farthest node from any apple node
        furthest_node, _ = bfs(start_node, graph, N)
        
        # Second BFS to find the maximum distance from this furthest node
        _, max_distance = bfs(furthest_node, graph, N)
        
        # The minimum time required is the maximum distance found
        results.append(str(max_distance))
    
    print("\n".join(results))

# Sample input processing
data = input().split()
T = int(data[0])
index = 1

test_cases = []
for _ in range(T):
    N = int(data[index])
    index += 1
    apple_nodes = list(map(int, data[index:index + N]))
    index += N
    edges = []
    for _ in range(N - 1):
        u = int(data[index]) - 1
        v = int(data[index + 1]) - 1
        edges.append((u, v))
        index += 2
    test_cases.append((N, apple_nodes, edges))

minimum_seconds_to_collect_apples(T, test_cases)

Information

Submit By
Type
Submission
Problem
P1078 Apple on Tree
Contest
Bangladesh 2.0
Language
Python 3 (Python 3.12.3)
Submit At
2024-08-16 16:22:36
Judged At
2024-10-03 13:27:13
Judged By
Score
0
Total Time
831ms
Peak Memory
93.828 MiB