Overview

Given dependencies between tasks (a directed graph) and the duration of each task, this problem asks for the earliest time at which all tasks can be completed (= the length of the critical path). If there is a cycle in the dependencies, it is impossible to complete all tasks, so output -1.

Analysis

Observation 1: This is a Longest Path Problem on a DAG

The prerequisite relation “Task \(U\) must be completed before starting Task \(V\)” can be viewed as a directed edge \(U \to V\).

Let \(f_i\) be the “earliest completion time of task \(i\)”. Then:

• If task \(i\) has no incoming edges (no prerequisites), it can start at time \(0\), so \(f_i = A_i\).
• Otherwise, for all prerequisites \(u \to i\), the condition \(S_i \ge f_u\) must hold, so the earliest start time is \(\max_{u \to i} f_u\), which gives: $\(f_i = \max_{u \to i} f_u + A_i\)$

The answer is \(\max_{1 \le i \le N} f_i\).

This is nothing other than finding the “maximum sum of \(A\) along a path from a vertex with in-degree \(0\) to \(i\)” in the graph—that is, finding the longest path in a DAG.

Observation 2: When is it Impossible?

Since \(S_{V} \ge S_U + A_U\) and \(A_i \ge 1\), following an edge strictly increases the start time. Therefore, the presence of a cycle leads to a contradiction, meaning no valid set of start times exists. Conversely, if there are no cycles (the graph is a DAG), setting \(S_i = f_i - A_i\) using the \(f_i\) values defined above satisfies all constraints.

Thus, “impossible \(\iff\) a cycle exists in the graph”.

Issues with Naive Approaches

• While the idea of “computing \(f_i\) using memoized recursion (DFS)” is conceptually correct, recursion to a depth of \(N = 2 \times 10^5\) in Python risks a stack overflow, and cycle detection would also need to be handled separately.
• “Simulating by advancing time by \(1\)” will not finish in time at all, as \(A_i \le 10^9\) means the answer can reach up to the order of \(10^{14}\).
• Representing the adjacency list as a list of lists like adj = [[] for _ in range(n+1)] tends to incur significant constant-factor overhead in Python (while it may pass under the constraints of this problem, the CSR format described below is safer).

By using topological sort (Kahn’s algorithm), we can perform cycle detection and longest path calculation simultaneously, non-recursively, in \(O(N+M)\) time.

Algorithm

We process the graph using Kahn’s algorithm (BFS-based topological sort).

1. Count the in-degree indeg[v] of each vertex.
2. Initialize finish[i] with \(A_i\) (the completion time when there are no prerequisites at all).
3. Push all vertices with indeg[i] == 0 into a queue.
4. Pop a vertex \(u\) from the queue. At this point, all incoming edges to \(u\) have already been processed, so finish[u] is finalized. Update the answer with ans = max(ans, finish[u]).
5. For each outgoing edge \(u \to v\) from \(u\):
   • finish[v] = max(finish[v], finish[u] + A[v])
   • indeg[v] -= 1; if it becomes \(0\), push \(v\) into the queue.
6. If the number of processed vertices is less than \(N\), there is a cycle, so output -1; otherwise, output ans.

Why it is correct: Because vertices are processed in topological order, by the time vertex \(v\) is popped from the queue, all incoming edges \(u \to v\) have already had their source \(u\) finalized and processed. Therefore, finish[v] correctly holds \(\max_{u \to v} f_u + A_v\).

Concrete Example

When \(N=4\), \(A = (3, 1, 4, 2)\), and the edges are \(1\to3, 2\to3, 3\to4\):

• indeg = (0,0,2,1), initial finish = (3,1,4,2)
• Process vertex \(1\): ans=3, finish[3] = max(4, 3+4) = 7, indeg[3]=1
• Process vertex \(2\): ans=3, finish[3] = max(7, 1+4) = 7, indeg[3]=0 \(\to\) push
• Process vertex \(3\): ans=7, finish[4] = max(2, 7+2) = 9, push
• Process vertex \(4\): ans=9

The answer is \(9\).

Complexity

• Time Complexity: \(O(N + M)\)
• Space Complexity: \(O(N + M)\)

Implementation Points

• Fast I/O: Read all input at once with sys.stdin.buffer.read().split(). With \(N = 2\times10^5\) and \(M = 10^5\) lines, calling input() repeatedly should be avoided.

• Representing the adjacency list in CSR (Compressed Sparse Row) format:

  start[i] : Starting index in adj where the outgoing edges of vertex i begin
  adj[start[i] : start[i+1]] : Sequence of destinations from vertex i
  

  First, count the out-degree cnt of each vertex, compute its prefix sums to build start, and iterate over the edges once more to populate adj. Compared to a list of lists in Python, this creates fewer objects and significantly reduces constant-factor overhead.

• Avoid recursion: Since this is a BFS-based approach using deque, it is safe even with a depth of \(2\times 10^5\) (recursive DFS carries the risk of a RecursionError).

• Cycle detection: Check if processed != n. Vertices involved in a cycle will never have an in-degree of \(0\), and thus will never be pushed into the queue.

• No need to worry about overflow: The maximum value can reach \(2\times10^5 \times 10^9 = 2\times10^{14}\), but Python integers have arbitrary precision so this is not an issue (in C++, long long must be used).

• Initializing finish with \(A_i\) eliminates the need to handle vertices with in-degree \(0\) (which start at time \(0\)) as a special case.

  Source Code

import sys
from collections import deque

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1
    A = [0]*(n+1)
    for i in range(1, n+1):
        A[i] = int(data[idx]); idx += 1
    indeg = [0]*(n+1)
    us = [0]*m
    vs = [0]*m
    cnt = [0]*(n+2)
    for j in range(m):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        us[j] = u
        vs[j] = v
        cnt[u] += 1
        indeg[v] += 1
    start = [0]*(n+2)
    s = 0
    for i in range(1, n+1):
        start[i] = s
        s += cnt[i]
    start[n+1] = s
    pos = start[:]
    adj = [0]*m
    for j in range(m):
        u = us[j]
        adj[pos[u]] = vs[j]
        pos[u] += 1

    finish = [0]*(n+1)
    for i in range(1, n+1):
        finish[i] = A[i]
    q = deque()
    for i in range(1, n+1):
        if indeg[i] == 0:
            q.append(i)
    processed = 0
    ans = 0
    while q:
        u = q.popleft()
        processed += 1
        fu = finish[u]
        if fu > ans:
            ans = fu
        for k in range(start[u], start[u+1]):
            v = adj[k]
            nf = fu + A[v]
            if nf > finish[v]:
                finish[v] = nf
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    if processed != n:
        sys.stdout.write("-1\n")
    else:
        sys.stdout.write(str(ans) + "\n")

main()

---

This editorial was generated by claude5opus-high.