Submission #1147610

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147610		vicvic	Cat in a tree (BOI17_catinatree)	C++20	100 / 100	68 ms	25412 KiB

catinatree

#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;
}

• Subtask 1: 11 / 11
• Subtask 2: 40 / 40
• Subtask 3: 49 / 49