Submission #1087822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087822		underwaterkillerwhale	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	51 ms	25940 KiB

catinatree

#include <bits/stdc++.h>
#define ll              long long
#define pii             pair<int,int>
#define pll             pair<ll,ll>
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)
#define iter(id, v)     for(auto id : v)
#define fs              first
#define se              second
#define MP              make_pair
#define pb              push_back
#define bit(msk, i)     ((msk >> i) & 1)
#define SZ(v)           (ll)v.size()
#define ALL(v)          v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 3e5 + 7;
const int Mod = 1e9 + 7;
const int INF = 1e9;
const ll BASE = 137;
const int szBL = 320;

int n, D;
vector<int> ke[N];
pii dp[N];

void dfs (int u, int p) {
    vector<pii> vec;
    iter (&v, ke[u]) {
        if (v != p) {
            dfs(v, u);
            if (dp[v].fs > 0) vec.pb(dp[v]);
        }
    }
    sort (ALL(vec), [] (pii A, pii B) { return A.se < B.se; });
    if (SZ(vec) == 0) dp[u] = {1, 1};
    else if (SZ(vec) == 1) {
        dp[u] = {vec[0].fs, vec[0].se + 1};
        if (vec[0].se >= D) {
            dp[u].fs++;
            dp[u].se = 1;
        }
    }
    else {
        int mn = INF;
        rep (i, 1, SZ(vec)) {
            if (i == SZ(vec) || vec[i].se + vec[i - 1].se >= D) {
                rep (j, i - 1, SZ(vec) - 1) {
                    dp[u].fs += vec[j].fs;
                    mn = min(mn, vec[j].se);
                }
                break;
            }
            else dp[u].fs += vec[i - 1].fs - 1;
        }
        if (mn >= D) {
            dp[u].fs++;
            dp[u].se = 1;
        }
        else dp[u].se = mn + 1;
    }
}

void solution() {
    cin >> n >> D;
    rep (i, 2, n) {
        int p;
        cin >> p;
        ++p;
        ke[p].pb(i);
        ke[i].pb(p);
    }
    dfs(1, 0);
    cout << dp[1].fs <<"\n";
}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("compete");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug +7
5 3 1
1 1 1 2 3
2 3 5
1 2
2 3
2 4
1 5
2 3
*/

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