Overview

This problem asks us to model task prerequisites as a directed graph, determine whether the graph contains a cycle, and find the earliest start time for each task in order using topological sort.

Analysis

Modeling as a Graph

Consider a directed graph where each task is a vertex and each prerequisite relation “Task \(V\) cannot be started until Task \(U\) is completed” is a directed edge \(U \to V\). The start time \(S_V\) of Task \(V\) must satisfy \(S_V \ge S_U + A_U\) for all tasks \(U\) preceding it.

To minimize the total completion time, it is optimal to start each task as early as possible. Therefore, the start time of each task is determined as follows: - Tasks with no prerequisites: Start at time \(0\) (\(S_V = 0\)) - Tasks with prerequisites: Start the moment all prerequisite tasks are completed (\(S_V = \max_{U \to V} (S_U + A_U)\))

Cycle Detection

If a cycle exists in the graph (e.g., a dependency loop such as Task \(1 \to 2 \to 3 \to 1\)), a contradiction arises where “Task \(1\) cannot start until Task \(1\) itself finishes,” meaning no valid set of start times exists. In this case, we must output -1. A graph without cycles is called a Directed Acyclic Graph (DAG).

Calculating Earliest Start Times

If the graph is a DAG, by performing a topological sort to order the vertices according to their dependencies, we can finalize the completion times of preceding tasks and sequentially calculate the earliest start times for subsequent tasks.

Algorithm

We use Kahn’s algorithm (topological sort via BFS), which manages in-degrees (the number of incoming edges to each vertex).

1. Initialization:
   • Count the in-degree of each vertex.
   • Initialize an array \(S\) representing the start time of each task with \(0\).
   • Push all vertices with an in-degree of \(0\) (vertices without prerequisite tasks) into a queue (deque).
2. Search using a Queue:
   • Pop a vertex \(u\) from the queue (at this point, \(S_u\) is finalized).
   • Increment the count of processed vertices count by \(1\).
   • Compute the finish time \(S_u + A_u\) of vertex \(u\), and for each outgoing edge \(u \to v\) from \(u\):
     • Update \(S_v\) to \(\max(S_v, S_u + A_u)\).
     • Decrement the in-degree of vertex \(v\) by \(1\).
     • If the in-degree of vertex \(v\) becomes \(0\), all prerequisites for vertex \(v\) have been processed, so push it into the queue.
3. Determining the Answer:
   • If the number of processed vertices count is less than \(N\), it means the graph contains a cycle and the process halted early, so output -1.
   • If count is equal to \(N\), start times for all tasks have been computed. The total completion time is the maximum of all tasks’ finish times, \(\max_{1 \le i \le N} (S_i + A_i)\), so output this value.

Complexity

• Time Complexity: \(O(N + M)\)
  • Constructing the graph takes \(O(N + M)\) time, and each vertex and edge is traversed exactly once using the queue. Thus, the overall time complexity is \(O(N + M)\), which easily runs within the time limit.
• Space Complexity: \(O(N + M)\)
  • \(O(N + M)\) memory is used to store the adjacency list, in-degree array, start time array \(S\), etc.

Implementation Notes

• Handling Large Values:

  • Since \(A_i\) can be up to \(10^9\), if \(N\) tasks are arranged in a chain, the finish time can reach up to \(2 \times 10^5 \times 10^9 = 2 \times 10^{14}\). In Python, integers automatically have arbitrary precision, so overflow is not an issue, but in languages like C++, a 64-bit integer type (long long) must be used.

• Avoiding Recursion Depth Limits:

  • Although it can also be implemented using DFS-based topological sort, because the number of vertices is large (\(N \le 2 \times 10^5\)), one must be careful about recursion limits (such as RecursionError in Python). By using BFS (Kahn’s algorithm), it can be implemented safely without worrying about recursion depth.

    Source Code

import sys
from collections import deque

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    A = [int(x) for x in input_data[2:2+N]]
    
    adj = [[] for _ in range(N)]
    in_degree = [0] * N
    
    idx = 2 + N
    for _ in range(M):
        u = int(input_data[idx]) - 1
        v = int(input_data[idx+1]) - 1
        adj[u].append(v)
        in_degree[v] += 1
        idx += 2
        
    queue = deque([i for i in range(N) if in_degree[i] == 0])
    S = [0] * N
    
    count = 0
    while queue:
        u = queue.popleft()
        count += 1
        finish_u = S[u] + A[u]
        for v in adj[u]:
            if finish_u > S[v]:
                S[v] = finish_u
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
                
    if count < N:
        print(-1)
    else:
        ans = 0
        for i in range(N):
            finish_i = S[i] + A[i]
            if finish_i > ans:
                ans = finish_i
        print(ans)

if __name__ == '__main__':
    main()

---

This editorial was generated by gemini-3.8-flash-high.