Submission #1261786

#TimeUsernameProblemLanguageResultExecution timeMemory
1261786euclidBurza (COCI16_burza)C++20
160 / 160
74 ms844 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back #define fi first #define se second #define vi vector<int> #define pii pair<int, int> #define pll pair<ll, ll> #define vl vector<ll> int n, k, cnt = 0; const int MN = 403, MS = (1<<20)+3, INF = 1e9 + 7; vi G[MN], deps[23]; pii range[MN]; //range of leaves that node i can cover int dep[MN]; int dp[MS]; //dp[state]: picking a node from each depth in state, //the maximum leaf i s.t. leaves 1-i are all covered void dfs1(int node, int fa) { // cout << node << '\n'; range[node].fi = INF; dep[node] = dep[fa]+1; deps[dep[node]].pb(node); if(dep[node] == k) { range[node] = {++cnt, cnt}; return; } for(int child : G[node]) { if(child == fa) continue; dfs1(child, node); range[node].fi = min(range[node].fi, range[child].fi); range[node].se = max(range[node].se, range[child].se); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> k; for(int i = 1; i < n; i++) { int u, v; cin >> u >> v; G[u].pb(v); G[v].pb(u); } if(k > 20) { cout << "DA" << '\n'; return 0; } dep[0] = -1; dfs1(1, 0); // cout << range[1].fi << ' ' << range[1].se << '\n'; for(int s = 1; s < (1<<k); s++) { for(int j = 0; j < k; j++) { int d = j+1; for(int node : deps[d]) { if((s&(1<<j))==0) continue; int ss = s^(1<<j); dp[s] = max(dp[s], dp[ss]); // if(s == 3 && j == 1) cout << node << ' ' << range[node].fi << ' ' << range[node].se << ' ' << dp[ss] << '\n'; if(range[node].fi-1 <= dp[ss]) dp[s] = max(dp[s], range[node].se); } } } // cout << dp[3] << '\n'; cout << (dp[(1<<k)-1]==cnt ? "DA":"NE") << '\n'; // 6 2 // 1 2 // 2 3 // 3 4 // 1 5 // 5 6 }
#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...