/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Wrong Answer 18ms 3.312 MiB
#2 Wrong Answer 18ms 3.387 MiB
#3 Wrong Answer 18ms 3.336 MiB
#4 Wrong Answer 28ms 4.414 MiB
#5 Wrong Answer 181ms 21.562 MiB
#6 Wrong Answer 301ms 35.352 MiB
#7 Wrong Answer 217ms 27.77 MiB
#8 Wrong Answer 142ms 14.941 MiB
#9 Wrong Answer 336ms 36.82 MiB
#10 Wrong Answer 361ms 41.738 MiB
#11 Wrong Answer 244ms 31.098 MiB
#12 Wrong Answer 301ms 34.953 MiB
#13 Wrong Answer 116ms 17.586 MiB
#14 Wrong Answer 435ms 46.188 MiB
#15 Wrong Answer 200ms 23.566 MiB
#16 Wrong Answer 112ms 15.793 MiB
#17 Wrong Answer 109ms 15.875 MiB
#18 Wrong Answer 108ms 15.801 MiB
#19 Wrong Answer 500ms 72.609 MiB
#20 Wrong Answer 509ms 72.652 MiB
#21 Wrong Answer 509ms 72.613 MiB
#22 Wrong Answer 566ms 93.957 MiB
#23 Wrong Answer 794ms 90.641 MiB
#24 Wrong Answer 816ms 90.785 MiB
#25 Wrong Answer 551ms 90.355 MiB
#26 Wrong Answer 43ms 7.664 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:23
Judged At
2024-10-03 13:27:15
Judged By
Score
0
Total Time
816ms
Peak Memory
93.957 MiB