There are n tasks to prepare a festival, numbered 1 to n.
Task i takes d_i minutes, and its materials arrive at minute r_i, so it cannot start before minute r_i.
You are given m conditions; a condition "a b" means task b can start only after task a has finished (from that very moment on).
The same condition may be given more than once, and following the conditions never leads back to where you started.
There are plenty of hands, so several tasks can be done at the same time, and a task once started is finished without a break.
The earliest start E_i of task i is the largest of r_i and the values E_j + d_j of the tasks j that must finish before task i.
The overall finish time T is the largest of E_i + d_i over all tasks.
The latest finish F_i of task i is T if no task has to wait for task i to finish; otherwise it is the smallest of F_j - d_j over the tasks j that have to wait for task i.
The slack of task i is F_i - d_i - E_i (how long its start can be put off without delaying the overall finish time).
In the example the materials of task 3 arrive at minute 5, so E_3 = 5, E_4 = 9 and T = 10. F_4 = 10, F_2 = F_3 = 9, and F_1 is the smaller of 9 - 2 and 9 - 4, which is 5, so the slack of task 1 is 5 - 3 - 0 = 2.
Find T and the slack of every task.
Input
The first line gives n and m separated by a space. The second line gives d_1 to d_n and the third line gives r_1 to r_n, separated by single spaces. Each of the next m lines gives one condition "a b". 1 ≤ n ≤ 5,000, 0 ≤ m ≤ 10,000, 1 ≤ d_i ≤ 1,000,000,000, 0 ≤ r_i ≤ 1,000,000,000, 1 ≤ a, b ≤ n, a ≠ b
Output
T on the first line. On the second line, the slack of tasks 1 to n separated by single spaces. Write numbers as plain digits without commas
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Topological order is used twice: once forward (take out tasks whose predecessors are all settled and push the earliest starts), and once through that same order backwards (pull the latest finishes). So instead of a separate queue, append to an 'order taken out' list and read it from the front: you get the queue and the record of the order in one. If you do use a queue: Python collections.deque (list.pop(0) shifts every later item and is slow), Java ArrayDeque, C# Queue<T>, C++ std::queue, and in JS, TS, C and Craykon a list with a 'head index'. Trap one: the times go past 32 bits. 5,000 tasks of a billion minutes in one chain finish at 5 trillion. Java and C# int wrap around with no error and give a wrong number, and in C and C++ it is undefined behaviour, so use long / long long. Python integers have no limit and JS, TS and Craykon numbers are exact up to 2^53 (about 9 quadrillion), so they just work. Trap two: a condition can go from a higher-numbered task to a lower one. If you compute in number order from task 1, you use values that are not settled yet. The order is not the task number but 'the order in which the count of remaining predecessors reached 0'. Trap three: when the same condition appears twice, do not merge it on one side only. If you put the following tasks in a Set so the two become one, count the predecessor only once as well. Count it per line and the count never reaches 0, so that task and everything after it never enter the queue. Appending twice and counting twice is the simple way. Trap four: the latest finish of a task that nothing waits for is not its own finish time but the overall finish time T. A side task that ends early has slack too. Trap five: the earliest start begins at the arrival time r_i, not at 0. That is why even a task on the longest chain can have slack (task 1 in the example). In Craykon, Console.ReadNumbers() reads a line of numbers into a list and NewList(n, total) makes a filled list.
Pythonmain.py · 47 lines
import sysfrom collections import dequedef main(): data = sys.stdin.buffer.read().split() n, m = int(data[0]), int(data[1]) d = [0] + [int(x) for x in data[2 : 2 + n]] start = [0] + [int(x) for x in data[2 + n : 2 + 2 * n]] # 가장 이른 시작(처음에는 재료 도착 시각) nxt = [[] for _ in range(n + 1)] indeg = [0] * (n + 1) pos = 2 + 2 * n for _ in range(m): a, b = int(data[pos]), int(data[pos + 1]) pos += 2 nxt[a].append(b) # 같은 조건이 두 번 나오면 두 번 넣고 두 번 센다 indeg[b] += 1 # 앞으로: 먼저 할 일이 모두 정해진 일부터 꺼내며 가장 이른 시작을 민다 order = [] queue = deque(i for i in range(1, n + 1) if indeg[i] == 0) while queue: a = queue.popleft() order.append(a) finish = start[a] + d[a] for b in nxt[a]: if finish > start[b]: start[b] = finish indeg[b] -= 1 if indeg[b] == 0: queue.append(b) total = max(start[i] + d[i] for i in range(1, n + 1)) # 뒤로: 꺼낸 차례를 거꾸로 돌며 가장 늦은 끝을 당긴다(뒤따르는 일이 없으면 total) late = [total] * (n + 1) for a in reversed(order): for b in nxt[a]: if late[b] - d[b] < late[a]: late[a] = late[b] - d[b] print(total) print(" ".join(str(late[i] - d[i] - start[i]) for i in range(1, n + 1)))main()
JavaScriptmain.js · 44 lines
const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter((s) => s !== "").map(Number);const n = data[0];const m = data[1];const d = [0];const start = [0]; // 가장 이른 시작(처음에는 재료 도착 시각)for (let i = 0; i < n; i++) { d.push(data[2 + i]); start.push(data[2 + n + i]);}const next = Array.from({ length: n + 1 }, () => []);const indeg = new Array(n + 1).fill(0);for (let e = 0; e < m; e++) { const a = data[2 + 2 * n + 2 * e]; const b = data[3 + 2 * n + 2 * e]; next[a].push(b); // 같은 조건이 두 번 나오면 두 번 넣고 두 번 센다 indeg[b]++;}// 앞으로: 먼저 할 일이 모두 정해진 일부터 꺼내며 가장 이른 시작을 민다const order = [];for (let i = 1; i <= n; i++) if (indeg[i] === 0) order.push(i);for (let head = 0; head < order.length; head++) { const a = order[head]; const finish = start[a] + d[a]; for (const b of next[a]) { if (finish > start[b]) start[b] = finish; if (--indeg[b] === 0) order.push(b); }}let total = 0;for (let i = 1; i <= n; i++) total = Math.max(total, start[i] + d[i]);// 뒤로: 꺼낸 차례를 거꾸로 돌며 가장 늦은 끝을 당긴다(뒤따르는 일이 없으면 total)const late = new Array(n + 1).fill(total);for (let k = order.length - 1; k >= 0; k--) { const a = order[k]; for (const b of next[a]) late[a] = Math.min(late[a], late[b] - d[b]);}const slack = [];for (let i = 1; i <= n; i++) slack.push(late[i] - d[i] - start[i]);console.log(total + "\n" + slack.join(" "));
TypeScriptmain.ts · 46 lines
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").split(/\s+/).filter((s) => s !== "").map(Number);const n = data[0];const m = data[1];const d: number[] = [0];const start: number[] = [0]; // 가장 이른 시작(처음에는 재료 도착 시각)for (let i = 0; i < n; i++) { d.push(data[2 + i]); start.push(data[2 + n + i]);}const next: number[][] = Array.from({ length: n + 1 }, (): number[] => []);const indeg: number[] = new Array<number>(n + 1).fill(0);for (let e = 0; e < m; e++) { const a = data[2 + 2 * n + 2 * e]; const b = data[3 + 2 * n + 2 * e]; next[a].push(b); // 같은 조건이 두 번 나오면 두 번 넣고 두 번 센다 indeg[b]++;}// 앞으로: 먼저 할 일이 모두 정해진 일부터 꺼내며 가장 이른 시작을 민다const order: number[] = [];for (let i = 1; i <= n; i++) if (indeg[i] === 0) order.push(i);for (let head = 0; head < order.length; head++) { const a = order[head]; const finish = start[a] + d[a]; for (const b of next[a]) { if (finish > start[b]) start[b] = finish; if (--indeg[b] === 0) order.push(b); }}let total = 0;for (let i = 1; i <= n; i++) total = Math.max(total, start[i] + d[i]);// 뒤로: 꺼낸 차례를 거꾸로 돌며 가장 늦은 끝을 당긴다(뒤따르는 일이 없으면 total)const late: number[] = new Array<number>(n + 1).fill(total);for (let k = order.length - 1; k >= 0; k--) { const a = order[k]; for (const b of next[a]) late[a] = Math.min(late[a], late[b] - d[b]);}const slack: number[] = [];for (let i = 1; i <= n; i++) slack.push(late[i] - d[i] - start[i]);console.log(total + "\n" + slack.join(" "));
JavaMain.java · 67 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); // 시각은 10^9을 여러 번 더하므로 long이어야 한다 long[] d = new long[n + 1]; long[] start = new long[n + 1]; // 가장 이른 시작(처음에는 재료 도착 시각) st = new StringTokenizer(br.readLine()); for (int i = 1; i <= n; i++) d[i] = Long.parseLong(st.nextToken()); st = new StringTokenizer(br.readLine()); for (int i = 1; i <= n; i++) start[i] = Long.parseLong(st.nextToken()); List<List<Integer>> next = new ArrayList<>(); for (int i = 0; i <= n; i++) next.add(new ArrayList<>()); int[] indeg = new int[n + 1]; for (int e = 0; e < m; e++) { st = new StringTokenizer(br.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); next.get(a).add(b); // 같은 조건이 두 번 나오면 두 번 넣고 두 번 센다 indeg[b]++; } // 앞으로: 먼저 할 일이 모두 정해진 일부터 꺼내며 가장 이른 시작을 민다 int[] order = new int[n]; int tail = 0; for (int i = 1; i <= n; i++) if (indeg[i] == 0) order[tail++] = i; for (int head = 0; head < tail; head++) { int a = order[head]; long finish = start[a] + d[a]; for (int b : next.get(a)) { if (finish > start[b]) start[b] = finish; if (--indeg[b] == 0) order[tail++] = b; } } long total = 0; for (int i = 1; i <= n; i++) total = Math.max(total, start[i] + d[i]); // 뒤로: 꺼낸 차례를 거꾸로 돌며 가장 늦은 끝을 당긴다(뒤따르는 일이 없으면 total) long[] late = new long[n + 1]; Arrays.fill(late, total); for (int k = tail - 1; k >= 0; k--) { int a = order[k]; for (int b : next.get(a)) late[a] = Math.min(late[a], late[b] - d[b]); } StringBuilder sb = new StringBuilder(); sb.append(total).append('\n'); for (int i = 1; i <= n; i++) { if (i > 1) sb.append(' '); sb.append(late[i] - d[i] - start[i]); } System.out.println(sb); }}
C#Main.cs · 69 lines
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { string[] t = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(t[0]); int m = int.Parse(t[1]); // 시각은 10^9을 여러 번 더하므로 long이어야 한다 long[] d = new long[n + 1]; long[] start = new long[n + 1]; // 가장 이른 시작(처음에는 재료 도착 시각) for (int i = 1; i <= n; i++) { d[i] = long.Parse(t[1 + i]); start[i] = long.Parse(t[1 + n + i]); } var next = new List<int>[n + 1]; for (int i = 0; i <= n; i++) next[i] = new List<int>(); int[] indeg = new int[n + 1]; for (int e = 0; e < m; e++) { int a = int.Parse(t[2 + 2 * n + 2 * e]); int b = int.Parse(t[3 + 2 * n + 2 * e]); next[a].Add(b); // 같은 조건이 두 번 나오면 두 번 넣고 두 번 센다 indeg[b]++; } // 앞으로: 먼저 할 일이 모두 정해진 일부터 꺼내며 가장 이른 시작을 민다 int[] order = new int[n]; int tail = 0; for (int i = 1; i <= n; i++) if (indeg[i] == 0) order[tail++] = i; for (int head = 0; head < tail; head++) { int a = order[head]; long finish = start[a] + d[a]; foreach (int b in next[a]) { if (finish > start[b]) start[b] = finish; if (--indeg[b] == 0) order[tail++] = b; } } long total = 0; for (int i = 1; i <= n; i++) total = Math.Max(total, start[i] + d[i]); // 뒤로: 꺼낸 차례를 거꾸로 돌며 가장 늦은 끝을 당긴다(뒤따르는 일이 없으면 total) long[] late = new long[n + 1]; Array.Fill(late, total); for (int k = tail - 1; k >= 0; k--) { int a = order[k]; foreach (int b in next[a]) late[a] = Math.Min(late[a], late[b] - d[b]); } var sb = new StringBuilder(); sb.Append(total).Append('\n'); for (int i = 1; i <= n; i++) { if (i > 1) sb.Append(' '); sb.Append(late[i] - d[i] - start[i]); } Console.WriteLine(sb); }}
C++main.cpp · 56 lines
#include <algorithm>#include <iostream>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; // 시각은 10^9을 여러 번 더하므로 long long이어야 한다 vector<long long> d(n + 1), start(n + 1); // start: 가장 이른 시작(처음에는 재료 도착 시각) for (int i = 1; i <= n; i++) cin >> d[i]; for (int i = 1; i <= n; i++) cin >> start[i]; vector<vector<int>> next(n + 1); vector<int> indeg(n + 1, 0); for (int e = 0; e < m; e++) { int a, b; cin >> a >> b; next[a].push_back(b); // 같은 조건이 두 번 나오면 두 번 넣고 두 번 센다 indeg[b]++; } // 앞으로: 먼저 할 일이 모두 정해진 일부터 꺼내며 가장 이른 시작을 민다 vector<int> order; order.reserve(n); for (int i = 1; i <= n; i++) if (indeg[i] == 0) order.push_back(i); for (size_t head = 0; head < order.size(); head++) { int a = order[head]; long long finish = start[a] + d[a]; for (int b : next[a]) { start[b] = max(start[b], finish); if (--indeg[b] == 0) order.push_back(b); } } long long total = 0; for (int i = 1; i <= n; i++) total = max(total, start[i] + d[i]); // 뒤로: 꺼낸 차례를 거꾸로 돌며 가장 늦은 끝을 당긴다(뒤따르는 일이 없으면 total) vector<long long> late(n + 1, total); for (int k = (int)order.size() - 1; k >= 0; k--) { int a = order[k]; for (int b : next[a]) late[a] = min(late[a], late[b] - d[b]); } cout << total << '\n'; for (int i = 1; i <= n; i++) { if (i > 1) cout << ' '; cout << late[i] - d[i] - start[i]; } cout << '\n'; return 0;}
Cmain.c · 67 lines
#include <stdio.h>#include <stdlib.h>int main(void) { int n, m; if (scanf("%d %d", &n, &m) != 2) return 1; // 시각은 10^9을 여러 번 더하므로 long long이어야 한다 long long *d = malloc(sizeof(long long) * (n + 1)); long long *start = malloc(sizeof(long long) * (n + 1)); // 가장 이른 시작 long long *late = malloc(sizeof(long long) * (n + 1)); // 가장 늦은 끝 for (int i = 1; i <= n; i++) scanf("%lld", &d[i]); for (int i = 1; i <= n; i++) scanf("%lld", &start[i]); // 인접 목록: head[a]에서 시작해 nxt[e]를 따라가면 a 뒤에 오는 일이 차례로 나온다 int *head = malloc(sizeof(int) * (n + 1)); int *to = malloc(sizeof(int) * (m + 1)); int *nxt = malloc(sizeof(int) * (m + 1)); int *indeg = calloc(n + 1, sizeof(int)); for (int i = 0; i <= n; i++) head[i] = -1; for (int e = 0; e < m; e++) { int a, b; scanf("%d %d", &a, &b); to[e] = b; // 같은 조건이 두 번 나오면 두 번 넣고 두 번 센다 nxt[e] = head[a]; head[a] = e; indeg[b]++; } // 앞으로: 먼저 할 일이 모두 정해진 일부터 꺼내며 가장 이른 시작을 민다 int *order = malloc(sizeof(int) * (n + 1)); int tail = 0; for (int i = 1; i <= n; i++) if (indeg[i] == 0) order[tail++] = i; for (int h = 0; h < tail; h++) { int a = order[h]; long long finish = start[a] + d[a]; for (int e = head[a]; e != -1; e = nxt[e]) { int b = to[e]; if (finish > start[b]) start[b] = finish; if (--indeg[b] == 0) order[tail++] = b; } } long long total = 0; for (int i = 1; i <= n; i++) { if (start[i] + d[i] > total) total = start[i] + d[i]; } // 뒤로: 꺼낸 차례를 거꾸로 돌며 가장 늦은 끝을 당긴다(뒤따르는 일이 없으면 total) for (int i = 1; i <= n; i++) late[i] = total; for (int k = tail - 1; k >= 0; k--) { int a = order[k]; for (int e = head[a]; e != -1; e = nxt[e]) { int b = to[e]; if (late[b] - d[b] < late[a]) late[a] = late[b] - d[b]; } } printf("%lld\n", total); for (int i = 1; i <= n; i++) { printf(i > 1 ? " %lld" : "%lld", late[i] - d[i] - start[i]); } printf("\n"); free(d); free(start); free(late); free(head); free(to); free(nxt); free(indeg); free(order); return 0;}
Craykonmain.cray · 70 lines
첫줄 = Console.ReadNumbers();n = 첫줄[0];m = 첫줄[1];d = Console.ReadNumbers(); // d[i - 1]: i번 일에 걸리는 시간start = Console.ReadNumbers(); // 가장 이른 시작(처음에는 재료 도착 시각)next = [];indeg = NewList(n, 0);for (i = 0; i < n; i++){ next.Add([]);}for (e = 0; e < m; e++){ ab = Console.ReadNumbers(); next[ab[0] - 1].Add(ab[1] - 1); // 같은 조건이 두 번 나오면 두 번 넣고 두 번 센다 indeg[ab[1] - 1] += 1;}// 앞으로: 먼저 할 일이 모두 정해진 일부터 꺼내며 가장 이른 시작을 민다order = [];for (i = 0; i < n; i++){ if (indeg[i] == 0) { order.Add(i); }}for (head = 0; head < order.Count; head++){ a = order[head]; finish = start[a] + d[a]; foreach (b in next[a]) { if (finish > start[b]) { start[b] = finish; } indeg[b] -= 1; if (indeg[b] == 0) { order.Add(b); } }}total = 0;for (i = 0; i < n; i++){ total = Mathf.Max(total, start[i] + d[i]);}// 뒤로: 꺼낸 차례를 거꾸로 돌며 가장 늦은 끝을 당긴다(뒤따르는 일이 없으면 total)late = NewList(n, total);for (k = order.Count - 1; k >= 0; k--){ a = order[k]; foreach (b in next[a]) { late[a] = Mathf.Min(late[a], late[b] - d[b]); }}slack = [];for (i = 0; i < n; i++){ slack.Add(late[i] - d[i] - start[i]);}Console.WriteLine(total);Console.WriteLine(slack.Join(" "));