Submission #885557

#	Time	Username	Problem	Language	Result	Execution time	Memory
885557		yusufhocaoglu	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	113 ms	42408 KiB

catinatree

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define ll long long
#define pri pair<int,int>
#define prl pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pair<int,int>>
#define vpl vector<pair<ll,ll>>
#define re return 0
#define sqrt sqrtl
struct node {
    vi adj;
    int ss = 0;
    int cn = -1;
};
int d;
vector<node> nodes;
void dfs(int x,int p) {
    if (nodes[x].adj.size()==1) {
        //leaf
        nodes[x].ss=1;
        nodes[x].cn = 0;
    }
    for (auto v: nodes[x].adj) {
        if (v==p) continue;
        dfs(v,x);
    }
    deque<pri> childnodes;
    for (auto v: nodes[x].adj) {
        if (v==p) continue;
        childnodes.push_back({nodes[v].cn+1,nodes[v].ss});
    }
    sort(childnodes.begin(),childnodes.end());
    childnodes.push_front({0,1});
    //cout<<childnodes.size()<<" "<<x<<endl;
    int ss2 = 0;
    int mnc = 1e9;
    while (childnodes.size()>1 && childnodes[0].first+childnodes[1].first < d) {
        ss2+=childnodes[0].second-1;
        mnc = min(mnc,childnodes[0].first + d);
        childnodes.pop_front();

    }
    while (childnodes.size()) {
        mnc = min(mnc,childnodes[0].first);
        ss2+=childnodes[0].second;
        childnodes.pop_front();
    }
    nodes[x].ss = ss2;
    nodes[x].cn = mnc;
    
}
int32_t main() {
    int n;cin>>n>>d;
    nodes = vector<node>(n);
    for (int i = 0;i<n-1;i++) {
        int u;cin>>u;
        nodes[u].adj.push_back(i+1);
        nodes[i+1].adj.push_back(u);
    }
    dfs(0,-1);
    cout<<nodes[0].ss<<endl;
    return 0;
}

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