Submission #1258393

#TimeUsernameProblemLanguageResultExecution timeMemory
1258393nai0610Cat in a tree (BOI17_catinatree)C++20
100 / 100
51 ms13636 KiB
#include <bits/stdc++.h> #define ll int64_t #define ld long double using namespace std; // const int maxn =2e5+5; const int mod = 1e9+7; // 998244353,1610612741 const ll inf = 1e18; const ld pi = atan(1.0L)*4; int n,d,res,mn[maxn]; vector<int> g[maxn]; void dfs(int u) { for (auto v:g[u]) { dfs(v); if (++mn[v]+mn[u]<d) res--,mn[u]=max(mn[u],mn[v]); else mn[u]=min(mn[u],mn[v]); } } int main() { // freopen("../input.inp","r",stdin); // freopen("output.out","w",stdout); ios::sync_with_stdio(false); cin.tie(nullptr); clock_t start,end; start=clock(); cin >>n>>d; res=n; for (int i=2;i<=n;i++) { int p; cin>>p; g[p+1].push_back(i); } dfs(1); cout <<res; end=clock(); ld dur=(ld)(end-start)/(ld)(CLOCKS_PER_SEC)*(1000.0L); cerr<<dur<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...