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()