Submission #553493

#	Time	Username	Problem	Language	Result	Execution time	Memory
553493		Talha_Taki	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	98 ms	21864 KiB

catinatree

#include <bits/stdc++.h>
 
using namespace std;
 
 
typedef long long ll;
typedef pair <int, int> pii;
 
vector <vector <int>> adj;
vector <pii> dp;

int d;

void dfs(int u) {
    if (adj[u].empty()) {
        dp[u] = make_pair(1, 0);
        return ;
    }

    int ans = 0;
    vector <pii> a;
    for(int v : adj[u]) {
        dfs(v);
        a.push_back(dp[v]);
        ans += dp[v].first;
    }

    sort(a.begin(), a.end(), [] (const pii &a, const pii &b) {
        return a.second < b.second;
    });

    int dist = a[0].second + 1;
    int size = adj[u].size();
    int i;
    for(i = 1; i < size; ++i) {
        if (a[i-1].second + 2 + a[i].second < d) {
            ans--;
            dist = a[i].second + 1;
        }
        else break;
    }

    if (a[i-1].second + 1 >= d) {
        ans++;
        dist = 0;
    }

    dp[u] = make_pair(ans, dist);
}

 
int main(const int argc, const char *argv[]) {
 
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n >> d;

    adj.resize(n);
    dp.resize(n);

    for(int i = 1; i < n; ++i) {
        int p;
        cin >> p;

        adj[p].push_back(i);
    }

    dfs(0);

    cout << dp[0].first;

    return 0;
}

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