Submission #1147610

#TimeUsernameProblemLanguageResultExecution timeMemory
1147610vicvicCat in a tree (BOI17_catinatree)C++20
100 / 100
68 ms25412 KiB
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector <int> vec[200005];
int n, d, s;
int dfs (int nod)
{
    s++;
    vector <int> colored;
    colored.push_back (0);
    for (auto adj : vec[nod])
    {
        colored.push_back (dfs (adj)+1);
    }
    int ptr=0;
    sort (colored.begin(), colored.end());
    while (ptr+1<colored.size() && colored[ptr]+colored[ptr+1]<d)
    {
        ptr++;
        s--;
    }
    return colored[ptr];
}
int main ()
{
    cin >> n >> d;
    for (int i=2;i<=n;i++)
    {
        int x;
        cin >> x;
        vec[x+1].push_back (i);
    }
    dfs (1);
    cout << s;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...