Submission #955718

#TimeUsernameProblemLanguageResultExecution timeMemory
955718TimAniBurza (COCI16_burza)C++17
160 / 160
38 ms860 KiB
//start-time: 2024-03-31 11:42:07 #include <bits/stdc++.h> using namespace std; using ll = long long; void solve(){ int N, K; cin >> N >> K; vector<vector<int>> tree(N); for(int i = 0; i < N - 1; i++){ int u, v; cin >> u >> v; u--; v--; tree[u].push_back(v); tree[v].push_back(u); } if(K * K >= N){ cout << "DA\n"; return; } vector<vector<int>> depths(K + 1); vector<array<int, 2>> intervals(N, {N + 1, 0}); int cnt = 0; auto dfs = [&](int u, int p, int d, auto&& dfs) -> bool { bool deepEnought = d == K; if(deepEnought){ cnt++; intervals[u][0] = cnt; intervals[u][1] = cnt; } for(auto v : tree[u]){ if(v != p && d < K){ deepEnought |= dfs(v, u, d + 1, dfs); if(deepEnought){ intervals[u][0] = min(intervals[v][0], intervals[u][0]); intervals[u][1] = max(intervals[v][1], intervals[u][1]); } } } if(deepEnought) depths[d].push_back(u); return deepEnought; }; dfs(0, -1, 0, dfs); // max # covered with depths specified from mask vector<int> dp(1 << K, 0); dp[0] = 0; for(int mask = 1; mask < (1 << K); mask++){ for(int depth = 0; depth < K; depth++){ if(mask & (1<<depth)){ int prev = dp[mask ^ (1<<depth)]; for(auto v : depths[depth + 1]){ auto [l, r] = intervals[v]; if(l <= prev + 1){ dp[mask] = max(dp[mask], r); } } } } if(dp[mask] == cnt){ cout << "DA\n"; return; } } cout << "NE\n"; } int main() { cin.tie(0)->sync_with_stdio(0); int T = 1; //cin >> T; while(T--) solve(); 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...