Submission #636678

#	Time	Username	Problem	Language	Result	Execution time	Memory
636678		tvladm2009	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	101 ms	18716 KiB

catinatree

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAX_N = 2 * 1e5;
vector<int> g[MAX_N + 1];
int dp[MAX_N + 1], dist[MAX_N + 1];
int n, d;

bool cmp(int x, int y) {
    return dist[x] < dist[y];
}

void dfs(int u, int p = -1) {
    if (g[u].size() == 0 || (g[u].size() == 1 && g[u][0] == p)) {
        dp[u] = 1;
        dist[u] = 0;
        return;
    }
    for (int v : g[u]) {
        if (v != p) {
            dfs(v, u);
        }
    }
    for (int v : g[u]) {
        if (v != p) {
            dp[u] += dp[v];
        }
    }
    sort(g[u].begin(), g[u].end(), cmp);
    int aux = g[u][0];
    if (g[u][0] == p) {
        aux = g[u][1];
    }
    for (int v : g[u]) {
        if (v != aux && v != p && dist[aux] + dist[v] + 2 < d) {
            dp[u]--;
            aux = v;
        }
    }
    dist[u] = dist[aux] + 1;
    if (dist[u] >= d) {
        dp[u]++;
        dist[u] = 0;
    }
}

int main() {
    cin >> n >> d;
    for (int i = 1; i <= n - 1; i++) {
        int x;
        cin >> x;
        g[x + 1].push_back(i + 1);
    }
    dfs(1);
    cout << dp[1];
    return 0;
}

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