Submission #914395

#TimeUsernameProblemLanguageResultExecution timeMemory
914395phlapBurza (COCI16_burza)C++17
0 / 160
2 ms860 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int M=1e9+7; set<int> adj[401]; pair<int, int> cover[401]; int leafnum[401]; vector<int> atdepth[401]; int maxdepth[401]; int dp[1<<20]; int c=0; int x, y; void prune(int a, int b, int c){ maxdepth[a]=c; for(auto i: adj[a]){ if(i==b) continue; prune(i, a, c+1); maxdepth[a]=max(maxdepth[a], maxdepth[i]); if(maxdepth[i]<y) adj[a].erase(i); } } void dfs(int a, int b, int d){ atdepth[d].push_back(a); cover[a]={LLONG_MAX/2, LLONG_MIN/2}; bool flag=true; for(auto i: adj[a]){ if(i==b) continue; flag=false; dfs(i, a, d+1); cover[a].first=min(cover[a].first, cover[i].first); cover[a].second=max(cover[a].second, cover[i].second); } if(flag){ leafnum[a]=++c; cover[a]={leafnum[a], leafnum[a]}; } } void solve(){ cin>>x>>y; for(int i=0; i<x-1; i++){ int a, b; cin>>a>>b; adj[a].insert(b); adj[b].insert(a); } if(y>=20){ cout<<"DA"; return; } prune(1, 0, 0); dfs(1, 0, 0); for(int i=0; i<(1<<y); i++){ for(int j=0; j<y; j++){ if(i&(1<<j)){ dp[i]=max(dp[i], dp[i^(1<<j)]); for(auto k: atdepth[j+1]){ if(cover[k].first<=dp[i^(1<<j)]+1) dp[i]=max(dp[i], cover[k].second); } } } } if(dp[(1<<y)-1]==c) cout<<"DA"; else cout<<"NE"; } signed main(){ //freopen("in", "r", stdin); //freopen("out", "w", stdout); cin.tie(0)->sync_with_stdio(0); int t=1; //cin>>t; while(t--) solve(); }
#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...