//https://oj.uz/problem/view/COCI16_burza
#include <iostream>
#include <set>
#include <climits>
#include <algorithm>
#include <vector>
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;
}
Compilation message
burza.cpp: In function 'int main()':
burza.cpp:11:18: error: 'memset' was not declared in this scope
11 | #define ms(x, a) memset(x, a, sizeof(x))
| ^~~~~~
burza.cpp:40:5: note: in expansion of macro 'ms'
40 | ms(l, INF);
| ^~
burza.cpp:7:1: note: 'memset' is defined in header '<cstring>'; did you forget to '#include <cstring>'?
6 | #include <vector>
+++ |+#include <cstring>
7 |
