Submission #791464

#	Time	Username	Problem	Language	Result	Execution time	Memory
791464		Cookie	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	51 ms	24208 KiB

catinatree

#include<bits/stdc++.h>
#include<fstream>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const int mxn = 2e5 + 5, base = 74;
const ll p = 31, mod = 1e9 + 7, inf = 1e9;
int n, d;
vt<int>adj[mxn + 1];
int depth[mxn + 1];
pii dp[mxn + 1];
void dfs(int s, int pre){
    vt<pii>cand;
    for(auto i: adj[s]){
        if(i != pre){
            depth[i] = depth[s] + 1;
            dfs(i, s);
            cand.pb(dp[i]);
        }
    }
    sort(cand.rbegin(), cand.rend());
    int mncan = -1, ans = 0, mndep = inf;
    for(auto [dep, res]: cand){
        if(dep >= mncan){
            ans += res;
            mncan = max(mncan, -dep + 2 * depth[s] + d); mndep = min(mndep, dep);
        }else{
            ans += res - 1; 
        }
    }
    if(depth[s] >= mncan){
        ans++; mndep = min(mndep, depth[s]);
    }
    dp[s] = make_pair(mndep, ans);
}
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> d;
    for(int i = 1; i < n; i++){
        int p; cin >> p;
        adj[p].pb(i);
    }
    dfs(0, -1);
    cout << dp[0].se;
    return(0);
}

Compilation message (stderr)

catinatree.cpp: In function 'void dfs(int, int)':
catinatree.cpp:37:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |     for(auto [dep, res]: cand){
      |              ^

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