Submission #1361304

#	Time	Username	Problem	Language	Result	Execution time	Memory
1361304		ziyad_alharbi	Cat in a tree (BOI17_catinatree)	C++20	100 / 100	131 ms	30120 KiB

catinatree

#include <bits/stdc++.h> 
using namespace std;
const int maxn=2e5+5;
int d[maxn],n,k,t[maxn],ans;
vector<int>v[maxn];
set<array<int,2>>st;
void dfs(int x,int s)
{
    if(t[x]>=s)return;
    t[x]=s;
    // cout<<x<<' '<<s<<'\n';
    for(auto i:v[x])if(t[i]<s-1)dfs(i,s-1);
}
void in(int x,int p)
{
    if(x!=p)d[x]=d[p]+1;
    st.insert({d[x],x});
    // cout<<x<<' '<<d[x]<<'\n';
    for(auto i:v[x])
    {
        // cout<<i<<'\n';
        if(i!=p)in(i,x);
    }
}
main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>k;
    for(int x=1;x<n;x++)
    {
        int a;
        cin>>a;
        v[x].push_back(a);
        v[a].push_back(x);
    }
    in(0,0);
    // cout<<st.size()<<'\n';
    while(st.size())
    {
        auto [vl,x]=*st.rbegin();
        st.erase({vl,x});
        if(t[x])continue;
        // cout<<vl<<' '<<x<<'\n';
        ans++;
        dfs(x,k);
    }
    cout<<ans<<'\n';
}

Compilation message (stderr)

catinatree.cpp:25:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   25 | main()
      | ^~~~

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