Overview

We are given \(N\) tasks, each with a required duration and prerequisite relations in the form of “task A cannot be started until task B is finished.” We need to find the earliest time at which all tasks are completed (the length of the critical path). If there is a cycle in the prerequisite relations, output \(-1\).

Analysis

Key Observation 1: Greedily Starting “As Early As Possible” Is Optimal

There is no benefit in delaying the start time \(S_i\) of each task. In fact, by setting it to the earliest possible time:

\[S_i = \max_{(u \to i) \in E} (S_u + A_u)\]

(or \(S_i = 0\) if there are no prerequisite tasks),

we satisfy all constraints \(S_{V_j} \ge S_{U_j} + A_{U_j}\) while simultaneously minimizing the completion time \(S_i + A_i\) of every task.

This is because, for any feasible solution \(S'\), we can show by induction along the topological order of prerequisites that “\(S_i \le S'_i\) holds for all \(i\).” Therefore, the answer is

\[\text{answer} = \max_{1 \le i \le N} (S_i + A_i)\]

This corresponds to finding the longest path on a directed graph (with vertex weights \(A_i\)), which is known as the PERT / Critical Path Method.

Key Observation 2: No Solution Exists If There Is a Cycle

If we view the prerequisite relations as directed edges \(U_j \to V_j\), no solution exists if this directed graph contains a cycle. For example, if \(1 \to 2 \to 1\), then $\(S_2 \ge S_1 + A_1 > S_1,\quad S_1 \ge S_2 + A_2 > S_2\)\( which leads to a contradiction (since \)A_i \ge 1 > 0\(, this is always contradictory). Conversely, if there are no cycles (i.e., it is a DAG), we can always construct a feasible solution by determining \)S_i$ in topological order using the formula above.

Therefore, “no solution exists \(\iff\) a cycle exists in the graph.”

Pitfalls of Naive Approaches

• Recursively computing the longest path from each task: Without memoization, the number of paths can be exponential, leading to TLE (with memoization, it becomes equivalent to the approach described below).
• Simulating by advancing time one unit at a time: Since \(A_i \le 10^9\), the time can reach up to around \(2 \times 10^{14}\), which will never finish in time.
• Negating edge weights to find shortest paths (Bellman-Ford): This runs in \(O(NM)\), which is too slow, and cycle detection is also required.

These can all be reduced to \(O(N+M)\) by utilizing the property that “if the graph is a DAG, a single pass in topological order is sufficient.”

Algorithm

We use Kahn’s algorithm (BFS-based topological sort) + DP.

1. Add each edge \(U_j \to V_j\) to an adjacency list, and count the in-degrees \(\mathrm{indeg}[V_j]\).
2. Initialize all \(S_i\) to \(0\).
3. Push all vertices with \(\mathrm{indeg}[i] = 0\) into a queue (tasks with no prerequisites, i.e., tasks that can start at time \(0\)).
4. Pop a vertex \(u\) from the queue and increment the count of processed vertices by \(1\). Calculate the completion time of \(u\) as \(f = S_u + A_u\). Then, for each outgoing edge \(u \to v\):
   • \(S_v \leftarrow \max(S_v, f)\)
   • Decrement \(\mathrm{indeg}[v]\) by \(1\). If it becomes \(0\), push \(v\) into the queue.
5. When the queue becomes empty, if the number of processed vertices is less than \(N\), there is a cycle, so output -1.
6. Otherwise, output \(\max_i (S_i + A_i)\).

The key point is that when vertex \(u\) is popped from the queue, all incoming edges to \(u\) have already been processed (\(\mathrm{indeg}[u]\) has reached \(0\)), so the value of \(S_u\) is already finalized.

Example

For \(N=4\), \(A = (3, 1, 4, 2)\), and edges \(1\to2, 1\to3, 2\to4, 3\to4\):

• \(\mathrm{indeg} = (0,1,1,2)\), so the queue is \(\{1\}\).
• \(u=1\): \(f = 0+3 = 3\). \(S_2 = 3\), \(S_3 = 3\); \(\mathrm{indeg}[2]\) and \(\mathrm{indeg}[3]\) become \(0\) and are pushed into the queue.
• \(u=2\): \(f = 3+1 = 4\). \(S_4 = 4\), \(\mathrm{indeg}[4] = 1\).
• \(u=3\): \(f = 3+4 = 7\). \(S_4 = \max(4,7) = 7\); \(\mathrm{indeg}[4] = 0\) and is pushed into the queue.
• \(u=4\): \(f = 7+2 = 9\).

The answer is \(\max(3, 4, 7, 9) = 9\). The path \(1 \to 3 \to 4\) is the critical path.

Complexity

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

Implementation Notes

• Integer Overflow: Since \(A_i \le 10^9\) and there can be up to \(N = 2\times10^5\) tasks along a path, the completion time can reach up to around \(2\times10^{14}\). This will overflow a 32-bit integer, so make sure to use a 64-bit integer (long long).

• Queue Implementation: Instead of std::queue, using a vector and advancing an index idx reduces memory allocation overhead and is faster (it also has the advantage of directly giving the topological ordering sequence).

• Adjacency List: Using a forward star representation with three arrays head/nxt/to (as in this code) has lighter allocation overhead and is faster than vector<vector<int>>. Of course, vector<vector<int>> is also plenty fast enough to pass within the time limits.

• Handling Isolated Vertices: Vertices with no edges have \(\mathrm{indeg}=0\), so they naturally enter the initial queue and are reflected in the answer with \(S_i = 0\) and completion time \(A_i\). When \(M=0\), the answer is \(\max_i A_i\).

• Cycle Detection: There is no need to implement a separate DFS; you can simply check whether the number of vertices popped during the topological sort reaches \(N\).

• Fast I/O: Since \(N\) can be around \(2\times10^5\), it is safer to use scanf/printf or untie cin (ios::sync_with_stdio(false)).

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, M;
    if(scanf("%d %d", &N, &M)!=2) return 0;
    vector<long long> A(N+1);
    for(int i=1;i<=N;i++){
        long long x; scanf("%lld",&x); A[i]=x;
    }
    vector<int> head(N+1,-1), nxt(M), to(M);
    vector<int> indeg(N+1,0);
    for(int j=0;j<M;j++){
        int u,v; scanf("%d %d",&u,&v);
        to[j]=v; nxt[j]=head[u]; head[u]=j;
        indeg[v]++;
    }
    vector<long long> start(N+1,0);
    vector<int> q; q.reserve(N);
    for(int i=1;i<=N;i++) if(indeg[i]==0) q.push_back(i);
    int cnt=0;
    for(size_t idx=0; idx<q.size(); idx++){
        int u=q[idx]; cnt++;
        long long f = start[u]+A[u];
        for(int e=head[u]; e!=-1; e=nxt[e]){
            int v=to[e];
            if(start[v]<f) start[v]=f;
            if(--indeg[v]==0) q.push_back(v);
        }
    }
    if(cnt!=N){ printf("-1\n"); return 0; }
    long long ans=0;
    for(int i=1;i<=N;i++) ans=max(ans,start[i]+A[i]);
    printf("%lld\n", ans);
    return 0;
}

---

This editorial was generated by claude5opus-high.