Submission #867200

#TimeUsernameProblemLanguageResultExecution timeMemory
867200KiFaH_HeLaLBurza (COCI16_burza)C++17
0 / 160
1 ms348 KiB
#include <bits/stdc++.h> #define ll long long #define ld double using namespace std; int n, k; vector<vector<int> > adj; vector<vector<bool> > dp; void solve(int a, int b){ for(auto x:adj[a])if(x!=b)solve(x, a); int cnt=0; for(auto x:adj[a])if(x!=b)++cnt; if(cnt<=1){ for(int i=1;i<=k;++i)dp[a][i]=true; return; } vector<bool> resl(adj[a].size()+1, false), resr(adj[a].size()+1, false); for(int j=2;j<=k;++j){ resl[0]=resr[adj[a].size()]=true; for(int i=0;i<(int)adj[a].size();++i){ if(adj[a][i]==b)resl[i+1]=resl[i]; else resl[i+1]=resl[i]&&dp[adj[a][i]][j-1]; } for(int i=adj[a].size()-1;i>=0;--i){ if(adj[a][i]==b)resr[i]=resr[i+1]; else resr[i]=resr[i+1]&&dp[adj[a][i]][j-1]; } bool ans=false; for(int i=0;i<(int)adj[a].size();++i){ if(adj[a][i]==b)continue; if(resl[i]&&resr[i+1])ans=true; } dp[a][j]=ans; } } int main() { ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); int Tc=1;//cin>>Tc; while(Tc--) { cin>>n>>k; adj.assign(n+1, vector<int>()); for(int i=1;i<n;++i){ int u, v;cin>>u>>v; adj[u].push_back(v); adj[v].push_back(u); } dp.assign(n+1, vector<bool>(k+1, false)); solve(1, 1); if(dp[1][k])cout<<"DA\n"; else cout<<"NE\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...