Submission #1260685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260685		DangKhoizzzz	Cat in a tree (BOI17_catinatree)	C++20	11 / 100	72 ms	19272 KiB

catinatree

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int maxn = 3e5 + 7;

int n, D, d[2005][2005];
vector <int> g[maxn];
vector <int> chosen;

void dfs_ans(int u, int p)
{
    for(int v: g[u])
    {
        if(v == p) continue;
        dfs_ans(v, u);
    }
    bool add = true;
    for(int node: chosen)
    {
        if(d[node][u] < D) add = false;
    }
    if(add) chosen.push_back(u);
}

void dfs(int u , int p , int root , int h)
{
    d[root][u] = h;
    for(int v: g[u])
    {
        if(v == p) continue;
        dfs(v , u , root , h+1);
    }
}

void solve()
{
    cin >> n >> D;
    for(int i = 1; i < n; i++)
    {
        int v;
        cin >> v;
        g[i+1].push_back(v+1);
        g[v+1].push_back(i+1);
    }
    for(int i = 1; i <= n; i++)
    {
        dfs(i , i , i , 0);
    }
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        dfs_ans(i , i);
        ans = max(ans , (int)(chosen.size()));
        chosen.clear();
    }
    cout << ans << '\n';
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

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