Submission #1205606

#TimeUsernameProblemLanguageResultExecution timeMemory
1205606PlayVoltzCat in a tree (BOI17_catinatree)C++20
100 / 100
32 ms10944 KiB
#include <cstdio> #include <stdio.h> #include <stdbool.h> #include <iostream> #include <map> #include <vector> #include <climits> #include <stack> #include <string> #include <queue> #include <algorithm> #include <set> #include <unordered_set> #include <unordered_map> #include <cmath> #include <cctype> #include <bitset> #include <iomanip> #include <cstring> #include <numeric> #include <cassert> using namespace std; #define int long long #define pii pair<int, int> #define mp make_pair #define pb push_back #define fi first #define se second int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, k, ans; cin>>n>>k, ans=n; vector<int> dp(n, 0); vector<vector<int> > graph(n); for (int i=1, a; i<n; ++i)cin>>a, graph[a].pb(i); for (int i=n-1; i>=0; --i)for (auto num:graph[i]){ if (dp[i]+dp[num]+1<k)dp[i]=max(dp[i], dp[num]+1), --ans; else dp[i]=min(dp[i], dp[num]+1); } cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...