Submission #732116

#TimeUsernameProblemLanguageResultExecution timeMemory
732116TrunktyCat in a tree (BOI17_catinatree)C++14
0 / 100
4 ms4936 KiB
#include <bits/extc++.h> using namespace std; typedef long long ll; #define int ll int n,d; vector<int> roads[200005]; int dp[200005],mini[200005]; void dfs(int x){ vector<int> v; for(int i:roads[x]){ dfs(i); dp[x] += dp[i]; v.push_back(mini[i]); } if(v.size()==0){ dp[x]++; } else{ sort(v.begin(),v.end(),greater<int>()); while(v.size()>=2){ int a = v.back(); v.pop_back(); if(a+v.back()+2LL<d){ dp[x]--; continue; } else{ v.push_back(a); break; } } if(v[0]+1LL<d){ mini[x] = v[0]+1LL; } else{ dp[x]++; } } } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> d; for(int i=1;i<=n-1;i++){ int a; cin >> a; roads[a].push_back(i); } dfs(0); cout << dp[0] << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...