Szczegółowe omówienie zadania Dyrektor patrzy:

Link do powyższego omówienia zadania Dyrektor patrzy: https://youtu.be/R4FOYOblSNE?t=1755
Omówienie kodu który zadania Dyrektor patrzy: https://youtu.be/R4FOYOblSNE?t=4104

Link do treści zadania Dyrektor patrzy i możliwości umieszczania rozwiązań:
https://szkopul.edu.pl/problemset/problem/NeHsbwV_Rok4bVgn9LjDoZR9/site

Zadanie Dyrektor patrzy pokazuje zastosowanie techniki Preorder / Postorder: https://youtu.be/R4FOYOblSNE?t=2901
Preorder/postorder pozwala na sprawdzenie zależności między wierzchołkami: https://youtu.be/R4FOYOblSNE?t=3515
Jak zrobić nasze zadanie korzystając z Preorder/Postorder? https://youtu.be/R4FOYOblSNE?t=3780
Złożoność rozwiązania z Preorder / Postorder:
https://youtu.be/R4FOYOblSNE?t=3937
Implementacja Preorder / Postorder w kodzie programu:
https://youtu.be/R4FOYOblSNE?t=4571

Technika Preorder / Postorder korzysta z algorytmu DFS: https://youtu.be/P4xemLnkDFc?t=1243
DFS jest przewidywalny i rozwiązuje nasz problem: https://youtu.be/R4FOYOblSNE?t=2743

Rozwiązanie brutalne – zamiast Preorder / Postorder: https://youtu.be/R4FOYOblSNE?t=2490

–
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 Dyrektor patrzy, który jest omówiony w powyższym filmie i który otrzymuje 100%

–

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 7;
vector<int> G[MAXN];
int pre[MAXN];
int post[MAXN];
int c = 1;
void DFS(int v, int p)
{
pre[v] = c;
++c;
for (auto u : G[v]) {
if (u != p)
DFS(u, v);
}
post[v] = c;
++c;
}
// czy a jest przodkiem b?
bool czy_przodek(int a, int b)
{
return (pre[a] < pre[b]) && (post[a] > post[b]);
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0);
int n, q;
cin >> n >> q;
for (int i = 2; i <= n; ++i) {
int p;
cin >> p;
G[i].push_back(p);
G[p].push_back(i);
}
DFS(1, 1);
for (int i = 1; i <= q; ++i) {
int a, b, c;
cin >> a >> b >> c;
bool ca = czy_przodek(c, a);
bool cb = czy_przodek(c, b);
if (ca && cb)
cout << "Dyrektor patrzy\n";
else if (ca)
cout << "Tylko B\n";
else if (cb)
cout << "Tylko A\n";
else
cout << "Droga wolna\n";
}
return 0;
}

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

from sys import setrecursionlimit
setrecursionlimit(500000)
c = 1
def DFS(v, p, G, pre, post):
global c
pre[v] = c
c += 1
for u in G[v]:
if (u != p):
DFS(u, v, G, pre, post)
post[v] = c
c += 1
def czy_przodek(a, b, pre, post):
return (pre[a] < pre[b]) and (post[a] > post[b])
def solve():
n, q = map(int, input().split())
G = [[] for i in range(n + 1)]
parrent = list(map(int, input().split()))
for i in range(n-1):
G[parrent[i]].append(i + 2)
G[i + 2].append(parrent[i])
pre = [0] * (n + 1)
post = [0] * (n + 1)
DFS(1, 1, G, pre, post)
for i in range(q):
a, b, c = map(int, input().split())
ca = czy_przodek(c, a, pre, post)
cb = czy_przodek(c, b, pre, post)
if (ca and cb):
print("Dyrektor patrzy")
elif (ca):
print("Tylko B")
elif (cb):
print("Tylko A")
else:
print("Droga wolna")
solve()