Overview

We represent the prerequisite relations as a directed graph and determine the earliest completion time of each task while performing a topological sort. If a directed cycle exists, the prerequisite relations cannot be satisfied, so we output -1.

Analysis

1. Representing Prerequisites as a Directed Graph

Let the tasks be vertices, and represent the prerequisite relation “task \(v\) can only start after task \(u\) is completed” as a directed edge \(u \to v\).

If this graph contains a directed cycle, it is impossible to complete all tasks. For example, if there is a relation \(1 \to 2 \to 3 \to 1\), every task must wait for another task to finish.

More strictly, summing the prerequisite inequalities along the cycle causes the start time terms to cancel out, resulting in \(0 \ge A_1 + A_2 + A_3\). Since all task durations are positive, this is a contradiction.

On the other hand, if there are no directed cycles, we can determine feasible start times by processing tasks in order starting from their prerequisites.

2. A Task Can Start Immediately After All Its Prerequisites Finish

There is no limit on the number of tasks that can be executed simultaneously. Therefore, there is no advantage in delaying tasks that are ready to start, and it is optimal to start each task as early as possible.

Let \(\mathrm{finish}[v]\) be the earliest completion time of task \(v\).

• If task \(v\) has no prerequisite tasks, it can start at time \(0\), so \(\mathrm{finish}[v] = A_v\).
• If task \(v\) has prerequisite tasks, all of them must be completed, so \(\mathrm{finish}[v] = \max_{u \to v}\mathrm{finish}[u] + A_v\).

Here, we take the maximum, not the sum, of the completion times of the prerequisite tasks. This is because the prerequisite tasks themselves can be executed in parallel.

For example, suppose tasks \(1, 2, 3\) have durations \(3, 5, 2\) respectively, with prerequisites \(1 \to 3\) and \(2 \to 3\). Tasks \(1\) and \(2\) can both start at time \(0\), and task \(3\) can start at time \(\max(3,5)=5\). Therefore, the overall completion time is \(5+2=7\).

3. Computing in Order from Prerequisite Tasks

Processing tasks simply in order of their indices does not guarantee that the completion times of their prerequisite tasks have already been computed. Furthermore, repeatedly scanning all tasks to find which ones can be started can take \(O(N^2)\) time if there are long chains of dependencies.

Therefore, we use topological sort. This is a technique to find an order of vertices in a directed graph such that for every directed edge \(u \to v\), vertex \(u\) is always processed before vertex \(v\).

Computing in this order ensures that when we process task \(v\), the earliest completion times of all its prerequisite tasks have already been finalized.

Since tasks cannot be completed earlier than the times determined by the equation above, and it is indeed feasible to execute them at these times, the maximum of \(\mathrm{finish}\) over all tasks will be the answer.

Algorithm

We combine topological sort using in-degrees and a queue (Kahn’s algorithm) with updating the completion times.

The in-degree is the number of incoming edges to a vertex. During execution, the in-degree represents the “number of prerequisite tasks that have not yet been processed.”

1. Add each prerequisite relation \(u \to v\) to the adjacency list and increase the in-degree of \(v\) by \(1\).
2. Initialize \(\mathrm{finish}[i] = A_i\) for all tasks.
3. Push all tasks with an in-degree of \(0\) into the queue.
4. While the queue is not empty, repeat the following:
   • Pop task \(u\), and increment the count of processed tasks by \(1\).
   • Update the candidate answer with \(\mathrm{answer} = \max(\mathrm{answer}, \mathrm{finish}[u])\).
   • For each edge \(u \to v\), do the following:
     • Update \(\mathrm{finish}[v] = \max(\mathrm{finish}[v], \mathrm{finish}[u] + A_v)\).
     • Decrease the in-degree of \(v\) by \(1\).
     • If the in-degree becomes \(0\), push \(v\) into the queue.
5. If the number of processed tasks is \(N\), output answer; otherwise, output -1.

By the time task \(v\) is pushed into the queue, updates from all of its prerequisite tasks are complete, so \(\mathrm{finish}[v]\) is finalized.

Furthermore, if not all tasks could be processed, there exists a directed cycle among the unprocessed tasks. In that case, it is impossible to set start times that satisfy all prerequisite relations.

Complexity

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

Each task enters the queue at most once, and each prerequisite relation is processed once. The space required for the adjacency list, completion times, in-degrees, and queue is also \(O(N+M)\) in total.

Implementation Notes

• Use 64-bit integers for completion times
  The completion time can be as large as the sum of all durations, potentially reaching \(N \times 10^9 \le 2 \times 10^{14}\). In the code, long long should be used for A, finish, and answer.

• Initialize finish with the durations
  The completion time of a task with no prerequisites is simply its duration. By initializing finish[i] = A[i] for all vertices, we can process updates with a uniform formula.

• Receive updates from all prerequisite tasks
  When a task has multiple prerequisites, it must wait for the one that finishes last. Make sure to update values using max rather than overwriting with an assignment.

• Use the count of processed tasks to detect cycles
  Even if only part of the graph contains a cycle, other tasks might still be processed. After the queue becomes empty, we need to check whether processed == N.

• No special handling is needed for \(M=0\)
  Since all tasks can start at time \(0\), the exact same logic naturally produces \(\max_i A_i\).

  Source Code

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

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

    int N, M;
    cin >> N >> M;

    vector<long long> A(N), finish(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        finish[i] = A[i];
    }

    vector<vector<int>> graph(N);
    vector<int> indegree(N, 0);

    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        graph[u].push_back(v);
        ++indegree[v];
    }

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

    int processed = 0;
    long long answer = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        ++processed;
        answer = max(answer, finish[u]);

        for (int v : graph[u]) {
            finish[v] = max(finish[v], finish[u] + A[v]);
            if (--indegree[v] == 0) q.push(v);
        }
    }

    cout << (processed == N ? answer : -1LL) << '\n';
    return 0;
}

---

This editorial was generated by gpt-6-astra-medium.