Submission #799613

#	Time	Username	Problem	Language	Result	Execution time	Memory
799613		winthemcut3	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	60 ms	28072 KiB

catinatree

#include <bits/stdc++.h>
#define FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define PB push_back
#define ALL(v) (v).begin(), (v).end()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define fi   first
#define se   second
#define BIT(x, i) (((x) >> (i)) & 1)
using namespace std;

/** END OF TEMPLATE **/

const int mxN = 2e5 + 5;
typedef pair<int, int> pii;
int n, k;
vector<int> g[mxN];
int f[mxN], d[mxN];
void dfs(int u, int par) {
    f[u] = 1;
    vector<int> t{0};
    for(int &v : g[u]) {
        if(v == par) continue;
        dfs(v, u);
        t.PB(d[v]);
        f[u] += f[v];
    }
    sort(ALL(t));
    //cerr << u << ' ' << t.size() << ' ' << f[u] << '\n';
    int pos = t.size() - 1;
    for(int i = 0; i <= (int)t.size()-2; i++) {
        if(t[i] + t[i+1] < k) f[u]--;
        else {
            pos = i;
            break;
        }
    }
    d[u] = t[pos] + 1;
   // cerr << u << ' ' << d[u] << ' ' << f[u] << '\n';
}
int main()
{
    FastIO;
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    cin >> n >> k;
    FOR(i, 2, n) {
        int x; cin >> x;
        g[i].PB(x+1); g[x+1].PB(i);
    }
    dfs(1, 0);
    cout << f[1];
    return 0;
}

/*

*/

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