Submission #711361

#	Time	Username	Problem	Language	Result	Execution time	Memory
711361		stevancv	Cat in a tree (BOI17_catinatree)	C++14	0 / 100	3 ms	5028 KiB

catinatree

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 2e5 + 5;
const int inf = 1e9;
vector<int> g[N], ans;
int dep[N], mx[N], k;
int Dfs(int s, int d) {
    for (int u : g[s]) {
        int nesto = Dfs(u, d + 1);
        if (nesto != inf) d = nesto + 1;
    }
    if (d >= k) {
        ans.push_back(s);
        //cout << " + " << s << en;
        return 0;
    }
    else if (!ans.empty() && dep[s] > dep[ans.back()]) {
        //cout << " - " << ans.back() << en;
        ans.pop_back();
        //cout << " + " << s << en;
        ans.push_back(s);
        return 0;
    }
    return d;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int p; cin >> p;
        g[p].push_back(i);
        dep[i] = dep[p] + 1;
    }
    for (int i = n - 1; i >= 0; i--) {
        mx[i] = dep[i];
        sort(g[i].begin(), g[i].end(), [&] (int xx, int yy) {
            return mx[xx] > mx[yy];
        });
        for (int j : g[i]) smax(mx[i], mx[j]);
    }
    Dfs(0, inf);
    cout << ans.size() << en;
    return 0;
}

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