Szczegółowe omówienie zadania Decorate Apple Tree:
Link do powyższego omówienia zadania Decorate Apple Tree:
https://youtu.be/OA8BeVFvaNU?t=2907
Link do treści zadania Decorate Apple Tree:
https://codeforces.com/contest/1056/problem/D
Link do wszystkich zadań z tego contestu:
https://codeforces.com/contest/1056
——
Zadanie Decorate Apple Tree pokazuje
- co to jest drzewo?
- jak chodzić po grafie (drzewie) – używa w tym celu algorytmu DFS?
——
Omówienie grafu / drzewa:
https://youtu.be/OA8BeVFvaNU?t=1006
Algorytm DFS:
https://youtu.be/OA8BeVFvaNU?t=4025
Implementacja DFS:
https://youtu.be/OA8BeVFvaNU?t=5623
https://youtu.be/OA8BeVFvaNU?t=1006
Algorytm DFS:
https://youtu.be/OA8BeVFvaNU?t=4025
Implementacja DFS:
https://youtu.be/OA8BeVFvaNU?t=5623
—–
Zadanie Decorate Apple Tree pochodzi z najpopularniejszej platformy algorytmiczno – programistycznej – Codeforces.
Poziom D to poziom finału Olimpiady Informatycznej Juniorów.
Zrobienie tego zadania daje piękny wpis w CV:
https://youtu.be/b5qWOUnM-fk?t=4809
Zadanie Decorate Apple Tree pochodzi z najpopularniejszej platformy algorytmiczno – programistycznej – Codeforces.
Poziom D to poziom finału Olimpiady Informatycznej Juniorów.
Zrobienie tego zadania daje piękny wpis w CV:
https://youtu.be/b5qWOUnM-fk?t=4809
——–
Zadanie omawia Michał Szeliga – laureat Olimpiady Informatycznej Juniorów:
https://youtu.be/OA8BeVFvaNU?t=830
——–
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
——-
–
#include <bits/stdc++.h>
using namespace std;
vector<int> sas[100001]; // Tablica sąsiedztwa
bool odw[100001]; //Czy dany wierzchołek był już odwiedzony DFS-em
int wy[100001]; // Wynik dla poddrzewa
void DFS(int v){
if ((v == 1 && int(sas[v].size()) == 0) || (v != 1 && int(sas[v].size()) == 1)) wy[v] = 1; // Sprawdź, czy jesteś liściem. Jeśli tak, ustaw wynik na 1.
odw[v] = true;
for (int syn : sas[v]){
if (odw[syn] != true){
DFS(syn); //Po tym, wynik dla syna jest już gotowy
wy[v] += wy[syn]; //Dodaj wynik poddrzewa syna do wyniku naszego poddrzewa
}
}
}
int main(){
int n; // n - ilość wierzchołków
cin>>n;
for (int i = 2 ; i <= n; i++){
int ojciec;
cin>>ojciec;
sas[ojciec].push_back(i);
sas[i].push_back(ojciec);
//Dodajemy ojca do naszych sąsiadów, dodajemy siebie do sąsiadów ojca
}// Wczytywanie krawędzi
DFS(1); //Puszczamy DFS dla korzenia
stable_sort(wy+1, wy+n+1); //Sortujemy tablicę wyników
for (int i = 1; i < n+1; i++) cout<<wy[i]<<" ";
}
Kod C++ programu Decorate Apple Tree, który jest omówiony w powyższym filmie i który otrzymuje 100%