/ SeriousOJ /

Record Detail

Time Exceeded


  
# Status Time Cost Memory Cost
#1 Wrong Answer 24ms 3.312 MiB
#2 Wrong Answer 25ms 3.352 MiB
#3 Wrong Answer 25ms 3.414 MiB
#4 Wrong Answer 41ms 4.574 MiB
#5 Wrong Answer 343ms 23.0 MiB
#6 Wrong Answer 727ms 36.684 MiB
#7 Wrong Answer 445ms 29.574 MiB
#8 Wrong Answer 253ms 15.02 MiB
#9 Wrong Answer 619ms 37.16 MiB
#10 Wrong Answer 753ms 43.23 MiB
#11 Wrong Answer 528ms 33.113 MiB
#12 Wrong Answer 598ms 36.266 MiB
#13 Wrong Answer 245ms 18.5 MiB
#14 Wrong Answer 829ms 48.168 MiB
#15 Wrong Answer 364ms 23.695 MiB
#16 Wrong Answer 197ms 16.504 MiB
#17 Wrong Answer 203ms 17.176 MiB
#18 Wrong Answer 197ms 17.156 MiB
#19 Wrong Answer 897ms 77.855 MiB
#20 Wrong Answer 970ms 77.84 MiB
#21 Wrong Answer 967ms 81.672 MiB
#22 Time Exceeded ≥1052ms ≥148.512 MiB
#23 Time Exceeded ≥1022ms ≥95.008 MiB
#24 Time Exceeded ≥1102ms ≥91.949 MiB
#25 Time Exceeded ≥1021ms ≥91.652 MiB
#26 Wrong Answer 75ms 8.934 MiB

Code

def minimum_seconds_to_collect_apples(T, test_cases):
    from sys import setrecursionlimit, stdin, stdout
    from collections import deque, defaultdict

    setrecursionlimit(300000)
    output = []

    def dfs(node, parent, graph, visited, apples, distances):
        visited[node] = True
        max_dist = 0
        max_node = node
        
        for neighbor in graph[node]:
            if not visited[neighbor]:
                dist = dfs(neighbor, node, graph, visited, apples, distances)
                if dist > max_dist:
                    max_dist = dist
                    max_node = neighbor
        
        distances[node] = max_dist
        return max_dist + 1

    for case in test_cases:
        N, apple_nodes, edges = case
        if not any(apple_nodes):
            output.append("0")
            continue
        
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        
        apples = [i for i in range(N) if apple_nodes[i]]
        
        # Start DFS from the first apple node to find the farthest apple node
        visited = [False] * N
        distances = [0] * N
        max_node = apples[0]
        dfs(max_node, -1, graph, visited, apple_nodes, distances)
        
        # Now find the farthest node from the previous farthest node
        visited = [False] * N
        distances = [0] * N
        max_dist = dfs(max_node, -1, graph, visited, apple_nodes, distances)
        
        output.append(str(max_dist - 1))
    
    stdout.write("\n".join(output) + "\n")

# Sample input processing
import sys
input = sys.stdin.read
data = input().strip().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:21:31
Judged At
2024-10-03 13:27:24
Judged By
Score
0
Total Time
≥1102ms
Peak Memory
≥148.512 MiB