Overview

This problem asks us to find the minimum completion time of the entire project by representing prerequisites as a directed graph, detecting cycles (determining whether the project is impossible to complete), and applying dynamic programming via topological sort (the longest path problem on a DAG).

Analysis

1. Reduction to a Graph

Consider a directed graph where tasks are vertices and prerequisite relations \(U_j \to V_j\) are directed edges. From the condition “Task \(U\) must be completed before Task \(V\) can start,” 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 overall completion time, it is optimal to start each task at the earliest possible time. Therefore, tasks with no prerequisites start at time \(0\), and the start time of a task \(V\) with prerequisites is determined as follows: $\(S_V = \max_{U \to V} (S_U + A_U)\)$

2. Cycle Detection (Determining Feasibility)

If a directed cycle exists in the graph, a deadlock occurs: “B cannot start until A finishes, and A cannot start until B finishes.” In this case, no valid assignment of start times satisfies all prerequisites, so we output -1.

3. Dynamic Programming on a DAG

If no cycle exists, this graph is a DAG (Directed Acyclic Graph). On a DAG, by processing tasks in topological order (updating values starting from the prerequisite tasks), we can uniquely determine the earliest start time for each task.

Algorithm

Using Kahn’s algorithm (BFS using in-degrees), we perform dynamic programming (DP) simultaneously with topological sorting.

1. Initialization:

   • Count the in-degree (number of prerequisite tasks) of each vertex.
   • Initialize an array dp[i] with \(0\), which records the earliest start time of each vertex \(i\).
   • Add vertices with an in-degree of \(0\) (tasks with no prerequisites) to a queue.

2. Traversal and Updates:

   • Pop a vertex \(u\) from the queue and increment the count of visited vertices by \(1\).
   • For each vertex \(v\) connected by an outgoing edge from \(u\):
     • Update the start time: dp[v] = max(dp[v], dp[u] + A[u])
     • Decrement the in-degree of \(v\) by \(1\).
     • If the in-degree of \(v\) becomes \(0\), it means all prerequisite tasks of \(v\) have been completed, so add \(v\) to the queue.

3. Verdict and Answer Calculation:

   • After the queue becomes empty, if the number of visited vertices is less than \(N\), a cycle exists, so output -1.
   • If the number of visited vertices is \(N\), the answer is the maximum completion time across all tasks: \(\max_{1 \le i \le N} (dp[i] + A_i)\).

Complexity

• Time Complexity: \(O(N + M)\)
  • Each vertex and each edge is visited at most once, which runs in linear time. This is sufficiently fast under the constraints \(N \le 2 \times 10^5, M \le 10^5\).
• Space Complexity: \(O(N + M)\)
  • This is the memory required to store the adjacency list representing the graph, the in-degree array, and the DP array.

Implementation Details

• Beware of Overflow:

  • The required time \(A_i\) for each task is up to \(10^9\). If the tasks are arranged in a line (in series), the completion time can reach up to \(N \times \max(A_i) \approx 2 \times 10^{14}\), which exceeds the range of a 32-bit integer (int). Therefore, a 64-bit integer type (long long in C++) must be used for the dp array and the answer calculation.

    Source Code

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<vector<int>> adj(n);
    vector<int> in_degree(n, 0);

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        adj[u].push_back(v);
        in_degree[v]++;
    }

    queue<int> q;
    for (int i = 0; i < n; ++i) {
        if (in_degree[i] == 0) {
            q.push(i);
        }
    }

    vector<long long> dp(n, 0);
    int visited_count = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        visited_count++;

        for (int v : adj[u]) {
            dp[v] = max(dp[v], dp[u] + a[u]);
            in_degree[v]--;
            if (in_degree[v] == 0) {
                q.push(v);
            }
        }
    }

    if (visited_count < n) {
        cout << -1 << "\n";
        return 0;
    }

    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        ans = max(ans, dp[i] + a[i]);
    }

    cout << ans << "\n";

    return 0;
}

---

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