Submission #924883

#	Time	Username	Problem	Language	Result	Execution time	Memory
924883		Muhammad_Aneeq	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	186 ms	103616 KiB

catinatree

/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int const N=2e5+10;
int const f=sqrt(N)+2;
vector<int>nei[N]={};
int h[N]={};
bool vis[N]={},vis1[N][f];
void dfs(int n,int dis,int pa=-1)
{
    if (dis==0)
        return ;   
    vis[n]=1;
    if (dis<f)
        vis1[n][dis]=1;
    for (auto i:nei[n])
    {
        if ((dis<f&&vis1[i][dis-1])||i==pa)
            continue;
        dfs(i,dis-1,n);
    }
}
inline void solve()
{
    int n,d;
    cin>>n>>d;
    h[0]=0;
    vector<pair<int,int>>d1={{0,0}};
    for (int i=0;i<n-1;i++)
    {
        int x;
        cin>>x;
        nei[i+1].push_back(x);
        nei[x].push_back(i+1);
        h[i+1]=h[x]+1;
        d1.push_back({h[i+1],i+1});
    }
    sort(begin(d1),end(d1));
    reverse(begin(d1),end(d1));
    int ans=0;
    for (auto i:d1)
    {
        if (!vis[i.second])
        {
            dfs(i.second,d);
            ans++;
        }
    }
    cout<<ans<<endl;
}   
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
        solve();
}

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