Submission #1193396

#TimeUsernameProblemLanguageResultExecution timeMemory
1193396akuygaCat in a tree (BOI17_catinatree)C++20
100 / 100
25 ms9920 KiB
#include "bits/stdc++.h" using namespace std; #define ii pair<int,int> #define f first #define s second #define mp make_pair #define ll long long int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); //they said that connected node will be always less than the node //so we can give the less one to always be parent int N,K; cin>>N>>K; vector<int> A[N]; for(int i=1;i<N;i++){ int x; cin>>x; A[x].push_back(i); } //using reverse idea we pick up node greedily and let's say we can't pick all node int c=N; vector<int> dp(N,0); //dp store depth for(int i=N-1;i>=0;i--){ for(auto n:A[i]){ if(dp[i]+dp[n]+1<K){ //in this case we can say we can't choose this pair together //so u gotta delete some and we will greedily delete parent(i) //that's the first time enter the case dp[i]=max(dp[i],dp[n]+1); //and when we store dp we store the leaf node which is farrest for sure //and we can consider to choose node c--; } else { //when enter this case let's say there are a pair dp[i]=min(dp[i],dp[n]+1); } } } cout<<c; // mark as unsolved I can't even describe how this will work gotta work more on this }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...