Submission #914043

#TimeUsernameProblemLanguageResultExecution timeMemory
914043duckierBurza (COCI16_burza)C++14
0 / 160
8 ms612 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int MAXN = 405, MAXK = 5, INF = 1e18; int n, k, cnt, dep[MAXN], mn[MAXN], mx[MAXN], dp[1<<MAXK]; vector<int> adj[MAXN]; void dfs(int x, int p, int d) { dep[x] = d; if(d==k){ cnt++; mn[x] = mx[x] = cnt; return; } for(int y : adj[x]) { if(y==p) continue; dfs(y, x, d + 1); mn[x] = min(mn[x], mn[y]); mx[x] = max(mx[x], mx[y]); } } signed main() { cin.tie(NULL)->sync_with_stdio(0); cin>>n>>k; if(k>20) { cout << "DA\n"; return 0; } for(int i = 1; i < n; i++) { int x, y; cin>>x>>y; adj[x].push_back(y); adj[y].push_back(x); } for(int i = 1; i <= n; i++) { mn[i] = INF; } dfs(1, 0, 0); for(int i= 1; i < (1<<k);i++) { for(int j = 0;j < k; j++) { if((i>>j)&1) { int pr = dp[i^(1<<j)]; for(int l= 1; l <= n; l++) { if(dep[l]!=j+1)continue; int cmn = mn[l], cmx = mx[l]; if(cmn <= pr + 1) { dp[i] = max(dp[i], cmx); } } } } } for(int i = 1; i < (1<<k); i++) { if(dp[i] >= cnt) { int counter = 0; for(int j = 0; j < k; j++) { if((i>>j)&1) counter++; } if(counter<=k) { cout << "DA\n"; return 0; } } } cout << "NE\n"; }
#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...