Submission #557870

#	Time	Username	Problem	Language	Result	Execution time	Memory
557870		fatemetmhr	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	70 ms	14704 KiB

catinatree

// ~Be name khoda~ //
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define pb     push_back
#define all(x) x.begin(), x.end()
#define fi     first
#define se     second
 
const int maxn5 = 2e5 + 10;
 
int d;
int cntbd2[maxn5], mn[maxn5], little[maxn5];
vector <int> adj[maxn5];
 
inline void dfs(int v){
    mn[v] = maxn5;
    little[v] = 0;
    for(auto u : adj[v]){
        dfs(u);
        cntbd2[v] += cntbd2[u];
        mn[v] = min(mn[v], mn[u]);
        little[v] = max(little[v], little[u]);
    }
    if(mn[v] + little[v] < d){
        little[v] = -1;
    }
    mn[v]++;
    if(little[v] != -1)
        little[v]++;
    if(little[v] * 2 >= d){
        cntbd2[v]++;
        mn[v] = little[v];
        little[v] = -1;
    }
    //cout << v << ' ' << cntbd2[v] << ' ' << mn[v] << ' ' << little[v] << endl;
    return;
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
    int n; cin >> n >> d;
    for(int i = 1; i < n; i++){
        int a; cin >> a;
        adj[a].pb(i);
    }
    dfs(0);
    cout << cntbd2[0] + (little[0] != -1) << endl;
}

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