Szczegółowe omówienie zadania Timeline:

Link do powyższego omówienia zadania Timeline: https://youtu.be/JXWWe0eYQCo?t=1072
Omówienie kodu zadania Timeline: https://youtu.be/JXWWe0eYQCo?t=4664
Link do treści zadania Timeline i możliwości umieszczania rozwiązań: http://www.usaco.org/index.php?page=viewproblem2&cpid=1017

Zadanie pokazuje wykorzystanie sortowania topologicznego: https://youtu.be/JXWWe0eYQCo?t=366
oraz programowanie dynamiczne: https://youtu.be/JXWWe0eYQCo?t=5058

Kolejne kroki rozwiązywania zadania:
1. Modelowanie procesu: https://youtu.be/JXWWe0eYQCo?t=1841
2. Kluczowa obserwacja – wierzchołki bez krawędzi wchodzących: https://youtu.be/JXWWe0eYQCo?t=2853
3. Kolejne kroki algorytmu: https://youtu.be/JXWWe0eYQCo?t=3008
4. Pseudokod: https://youtu.be/JXWWe0eYQCo?t=4104
5. Złożoność: https://youtu.be/JXWWe0eYQCo?t=4028

Uwagi
– Warto dokładnie czytać treść zadania: https://youtu.be/JXWWe0eYQCo?t=2367
– Kiedy wskazanie na sortowanie topologiczne? https://youtu.be/JXWWe0eYQCo?t=2410
– Na czym polega rozwiązywanie zadań? https://youtu.be/JXWWe0eYQCo?t=2476
– Jakie są zadania? https://youtu.be/JXWWe0eYQCo?t=5970

Zadanie z Amerykańskiej Olimpiady USACO! https://youtu.be/VvJhOAXIQOk?t=156
Pozwala stworzyć fantastyczne CV! https://youtu.be/XQcYAuPheVM?t=5642

–
Jak się uczyć na podstawie tego zadania? https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz: https://youtu.be/pkLXuuOe_qA?t=3625

Lista zadań z rozwiązaniami: https://oki.org.pl/lista-zadan-materialy.php
Samouczek – przygotowanie do Olimpiad: https://oki.org.pl/tutorial/

Zajęcia: https://oki.org.pl/harmonogram-zajec/
Informacje o zajęciach: https://oki.org.pl/newsletter.php

Warto startować w Olimpiadzie Informatycznej!
https://youtu.be/K7fZfJ8nN6A?t=109

–
Kod C++ programu "Timeline", który jest omówiony w powyższym filmie i który otrzymuje 100%

–

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

const int MAXN = 1e5 + 7;

vector<pair<int, int>> G[MAXN];
int kiedy[MAXN];
int stopien[MAXN];

int main()
{
	ifstream in("timeline.in");
	ofstream out("timeline.out");

	int n, m, c;
	in >> n >> m >> c;
	for (int i = 1; i <= n; ++i)
		in >> kiedy[i];
	for (int i = 1; i <= c; ++i) {
		int a, b, x;
		in >> a >> b >> x;
		G[a].push_back({b, x});
		++stopien[b];
	}

	stack<int> gotowe;
	for (int v = 1; v <= n; ++v) {
		if (stopien[v] == 0)
			gotowe.push(v);
	}
	while (!gotowe.empty()) {
		int v = gotowe.top();
		gotowe.pop();
		for (int i = 0; i < G[v].size(); ++i) {
			int u = G[v][i].first;
			int x = G[v][i].second;
			--stopien[u];
			if (stopien[u] == 0)
				gotowe.push(u);

			// aktualizujemy czas - uwzgledniamy dana krawedz
			kiedy[u] = max(kiedy[u], kiedy[v] + x);
		}
	}

	for (int v = 1; v <= n; ++v)
		out << kiedy[v] << '\n';
	return 0;
}

–
Kod Python programu Timeline, który otrzymuje 100%:

def solve():
	wejscie = open("timeline.in", "r")
	wyjscie = open("timeline.out", "w")

	n, m, c = map(int, wejscie.readline().split())
	G = [[] for i in range(n+1)]
	stopien = [0] * (n+1)
	kiedy = [0] + list(map(int, wejscie.readline().split()))
	for i in range(c):
		a, b, x = map(int, wejscie.readline().split())
		G[a].append([b, x])
		stopien[b] += 1

	gotowe = []
	for v in range(1, n+1):
		if (stopien[v] == 0):
			gotowe.append(v)

	while (len(gotowe) > 0):
		v = gotowe[-1]
		gotowe.pop()
		for u, x in G[v]:
			stopien[u] -= 1
			if (stopien[u] == 0):
				gotowe.append(u)
			kiedy[u] = max(kiedy[u], kiedy[v] + x)

	for v in range(1, n+1):
		wyjscie.write(str(kiedy[v]) + "\n")

solve()