Submission #1217805

#TimeUsernameProblemLanguageResultExecution timeMemory
1217805sam230609Burza (COCI16_burza)C++20
0 / 160
220 ms940 KiB
#include <bits/stdc++.h> using namespace std; const int INF=0x3f3f3f3f; vector<int> adj[401]; int dep[401],dp[1<<19],l[401],r[401],curr,n,k; void dfs(int v, int p){ if(dep[v]==k) {l[v]=r[v]=++curr; return; } for(int u:adj[v]){ if(u==p) continue; dep[u]=dep[v]+1; dfs(u,v); l[v]=min(l[v],l[u]); r[v]=max(r[v],r[u]); } } int main(){ cin >>n>>k; memset(l,INF,sizeof(l)); memset(r,0,sizeof(r)); if(k>=20) {cout <<"NE\n"; return 0;} for(int i=1;i<n;i++){ int a,b; cin >>a>>b; adj[a].push_back(b); adj[b].push_back(a); }dfs(1,-1); for(int mask=1;mask<(1<<k);mask++){ dp[mask]=-INF; for(int i=1;i<=n;i++){ if(!dep[i] || !(mask&(1<<(dep[i]-1)))) continue; if(dp[mask^(1<<(dep[i]-1))]+1>=l[i]) dp[mask]=max({dp[mask],r[i],dp[mask^(1<<(dep[i]-1))]}); } }cout <<(dp[(1<<k)-1]==curr?"DA":"NE"); }
#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...