Submission #821276

#TimeUsernameProblemLanguageResultExecution timeMemory
821276Jan636Burza (COCI16_burza)C++14
0 / 160
14 ms600 KiB
//https://oj.uz/problem/view/COCI16_burza #include <iostream> #include <set> #include <climits> #include <algorithm> #include <vector> #include <cstring> using namespace std; #define rep(i, n) for(int i=0; i<n; i++) #define ms(x, a) memset(x, a, sizeof(x)) const int INF=1e9; const int MAX=405; vector<int> adj[MAX]; int dep[MAX], dp[1<<19], l[MAX], r[MAX], 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(){ iostream::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> k; ms(l, INF); ms(r, 0); if(k>=20){ cout << "NE"; return 0; } rep(i, n-1){ 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(dep[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"); 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...