Submission #1251111

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251111		nrg_studio	Cat in a tree (BOI17_catinatree)	C++20	100 / 100	61 ms	21572 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define all(x) x.begin(),x.end()
#define vec vector

const int N = 2e5;
int ans = 0;
int dp[N];
vec<int> adj[N];
int d;

void dfs(int cur=0) {
    vec<int> dist;
    for (int x : adj[cur]) {
        dfs(x);
        dist.pb(++dp[x]);
    }
    sort(all(dist),greater<>());
    dp[cur] = d;
    for (int x : dist) {
        if (x+dp[cur]<d) {
            ans--;
        } else {
            dp[cur] = x;
        }
    }
    if (dp[cur]==d) {
        ans++;
        dp[cur] = 0;
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    
    int n; cin >> n >> d;
    for (int i=0;i<n-1;i++) {
        int p; cin >> p;
        adj[p].pb(i+1);
    }
    dfs();
    cout << ans << '\n';


    /*
    claim: add to deepest node
    if deepest node is unique then obviously do it
    if two deepest nodes, then marking one either marks other or no
    if other isn't marked, then they're independent
    else, they mark the same set of nodes (since they're at the same depth)
    proof: group deepest nodes where marking any node in one group marks the same set of nodes
    all groups are independent: is proved

    need an efficient way to do this
    try something
    */
}

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