Mam takie zadanie:
W Bajtocji ostatnimi czasy nie dzieje się najlepiej. Do władzy doszedł opanowany obsesyjnym strachem o swoje życie król Bitogrom. Już w kilka dni po objęciu tronu ukazał on swoje bezwzględne oblicze, ścinając pięciu dworzan podejrzanych o spiskowanie przeciw niemu. Na wszystkich urzędników w państwie padł strach o własne życie. Mieli oni świadomość, że każdy donos przełożonego prowadzi do szybkiej egzekucji. Sprawę pogarszał fakt, że donosiciel stawał się zaufanym człowiekiem króla, któremu tym samym nie groził już wyrok skazujący. W zastraszonym środowisku urzędników państwowych była to wystarczająca motywacja, żeby donieść na któregoś ze swoich podwładnych. Sytuacja w urzędach bardzo zmartwiła profesora Bajtoszewskiego, który przewidywał związane z nią utrudnienia w działaniu sektorów państwowych. Poprosił Cię, abyś obliczył, ilu maksymalnie urzędników może zostać straconych wskutek donosów. Profesor wyjaśnił Ci dokładniej zasady funkcjonowania państwa:
•Każdy z n urzędników w państwie ma unikatowy identyfikator będący liczbą całkowitą z przedziału [1, n].
•Każdy przełożony ma numer mniejszy od numerów wszystkich swoich podwładnych.
•Przełożonym wszystkich urzędników jest premier Bajtocji, który ma numer 1 i, tym samym, nie ma przełożonego.
•Każdy urzędnik donosi na co najwyżej jednego ze swoich podwładnych, ponieważ po pierwszym donosie
jest on już zaufanym człowiekiem króla.
•W Bajtocji panuje zasada: „podwładny mojego podwładnego jest moim podwładnym”, co w praktyce oznacza, że urzędnik może donieść na urzędnika, dla którego jest przełożonym tylko pośrednio.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita n (1 <= n <= 1 000 000) oznaczająca liczbę urzędników. W drugim wierszu znajduje się n − 1 liczb całkowitych, z których i-ta oznacza numer przełożonego urzędnika o numerze i + 1.
Wyjście
W pierwszym i jedynym wierszu standardowego wyjścia powinna znaleźć się jedna liczba całkowita, będąca maksymalną liczbą urzędników, którzy mogą zostać straceni w wyniku donosów.
Przykład
Dla danych wejściowych:
4
1 2 2
poprawnym wynikiem jest:
2
Wyjaśnienie do przykładu:
Urzędnik numer 1 donosi na urzędnika numer 3, a urzędnik numer 2 na urzędnika numer 4.
No i odpowiedź:
Jeśli u nie ma żadnych podwładnych, to wtedy oczywiście rozw[ u ] = 0, ponieważ nie doniesie on sam na siebie. Załóżmy teraz, że u ma bezpośrednich podwładnych u1 ,u2 ,...,uk, k 1 i przyjmijmy, że realizujemy scenariusz „zapisany” w każdej z komórek tablicy rozw[] odpowiadających bezpośrednim podwładnym u. Oznaczmy s = rozw[u1] +...+rozw[uk]. Wtedy mamy dwie możliwości:
•Każdy urzędnik w poddrzewie u (oprócz niego samego) doniósł na kogoś bądź był ofiarą donosu. Jest to równoznaczne temu, że liczba 2s + 1 jest rozmiarem całego poddrzewa u (liczbą urzędników w nim się znajdujących). Wtedy rozmiar ten jest nieparzysty i niemożliwym jest, by w tym drzewie dokonano więcej niż s donosów — możemy więc wtedy bezpiecznie przyjąć, że u nie donosi na nikogo, oraz rozw[u] = s.
•W przeciwnym wypadku liczba 2s + 1 jest mniejsza niż rozmiar całego poddrzewa, a więc jest w n im urzędnik, na którego u może donieść, dając sumaryczną liczbę donosów równą s + 1. Większej liczby donosów w tym poddrzewie nie można osiągnąć, bo to by oznaczało, że w pewnym poddrzewie ui można osiągnąć więcej ofiar niż rozw[ui].
Otrzymujemy więc prosty sposób na obliczenie rozw[u]. Jeśli 2s +1 jest równe rozmiarowi poddrzewa u, to rozw[ u ] = s , a w przeciwnym wypadku rozw[u] = s + 1.Pozostaje jeszcze problem szybkiego obliczania wielkości poddrzew. Nachalne przechodzenie całego poddrzewa każdego urzędnika zajmie w sumie czas kwadratowy ze względu na n , co jest zbyt kosztowne. Jednak i tutaj możemy posłużyć się programowaniem dynamicznym. Oznaczmy przez size[u]rozmiar poddrzewa ui rozpatrzmy dwa przypadki, takie jak poprzednio:
•u nie ma żadnych podwładnych — wtedy size[u] = 1;
• bezpośrednimi podwładnymi u są u1 ,u2 ,...,uk , k 1 — wtedy size[u] = 1 + size[u1] + ... + size[uk] .
W ten sposób otrzymujemy rozwiązanie o koszcie czasowym O(n)
Mam taki kod:
#include <bits/stdc++.h>
using namespace std;
int suma_poddanych(vector<int> & poddani, vector<int> & dp){
int s = 0;
for (auto poddany : poddani)
s += dp[poddany];
return s;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
int n, przelozony, s;
cin >> n;
vector<vector<int>> hierarchia(n+1);
for (int id_urzednika = 2; id_urzednika <= n; id_urzednika++){
cin >> przelozony;
hierarchia[przelozony].push_back(id_urzednika);
}
vector<int> l_pod(n+1);
for (int u = n; u > 0; u--){
if (hierarchia[u].size() == 0)
l_pod[u] = 1;
else
l_pod[u] = suma_poddanych(hierarchia[u], l_pod) + 1;
}
vector<int> rozw(n+1, 0);
for (int u = n; u > 0; u--){
if (l_pod[u] > 1){
s = suma_poddanych(hierarchia[u], rozw);
if (2 * s + 1 < l_pod[u])
rozw[u] = s + 1;
else
rozw[u] = s;
}
}
cout << rozw[1];
return 0;
}
Ale w jednym teście przekraczam limit pamięci a w kilku limit czasu, wydaje mi się że powinienem zrobić to jakoś bez wektora hierarchia ale nie wiem jak bez niego odnosić się do bezpośrednich pod-urzędników. Pomoże mi ktoś usprawnić ten kod?
Tutaj testuje
EDIT: Źle przekazywałem wektory, powinienem przez referencje a przekazywałem przez kopię, teraz tylko dwa testy nie przechodzą, w jednym przekroczenie limitu czasu w drugim limitu pamięci