Szczegółowe omówienie zadania Jumbo:

Link do powyższego omówienia zadania Jumbo:
https://youtu.be/I_Dr_vEnt2A?t=2950

Link do treści zadania Jumbo:
https://ki.staszic.waw.pl/task.php?name=jumbo

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

Zadanie omawia Michał Szeliga – laureat Olimpiady Informatycznej Juniorów:
https://youtu.be/OA8BeVFvaNU?t=830

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> sas[100000];
int pre[100000];
int post[100000];
bool vis[100000]; //Czy odwiedzony?
int krzykniecie = 0;
void DFS(int v){
vis[v] = 1;
pre[v] = ++krzykniecie; //Zwiększ krzyknięcie o 1, ustaw pre[v] na krzyknięcie
for (int u : sas[v]){
if (vis[u] == false){
DFS(u);
}
}
post[v] = ++krzykniecie;	
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
for (int i = 1; i < n; i++){
int ojciec;
cin>>ojciec;
sas[ojciec].push_back(i);
sas[i].push_back(ojciec);
}
DFS(0);
while (true){
int a,b;
cin>>a;
if (a == -1) return 0;
cin>>b;
if (pre[a] < pre[b] && post[a] > post[b]) cout<<"TAK\n";
else cout<<"NIE\n";
}
}

Kod C++ Darii, uczestniczki naszych zajęć, który otrzymuje 100%:

Bardzo dziękuję za pomoc w trakcie zajęć!

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 6;
vector idole[MAX_N];
int preOrder[MAX_N];
int postOrder[MAX_N];
bool odwiedzone[MAX_N];
int pre = 0;
int post = 0;
void DFS(int start) {
pre++;
preOrder[start] = pre;
odwiedzone[start] = true;
for (int i : idole[start]) {
if (!odwiedzone[i]) {
DFS(i);
post++;
}
}
postOrder[start] = post;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
int a, b;
cin >> n;
int idol;
for (int i = 1; i < n; ++i) { cin >> idol;
idole[idol].push_back(i);
}
DFS(0);
while (true) {
cin >> a;
if (a == -1) {
break;
}
cin >> b;
if (preOrder[a] < preOrder[b] && postOrder[a] > postOrder[b]) {
cout << "TAK" << "\n";
} else {
cout << "NIE" << "\n";
}
}
return 0;
}