#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <cassert>
#include <math.h>
using namespace std;
#define endl "\n"
#define int int64_t
#define pb push_back
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define FOR0(i,a) FOR(i,0,a)
#define FOR1(i,a) for (int i = (1); i <= (a); ++i)
#define TRAV(a,x) for (auto& a: x)
using pii = pair<int,int>;
using vi = vector<int>;
void printBin(int n, int len){
cout<<"(";
bool prev=false;
for(int i=0;i<=len;i++){
if(n & (1<<i)){
if(prev)
cout<<",";
cout<<i;
prev=true;
}
}
cout<<")";
}
int N,K;
vector<vector<int>> adj;
vector<vector<int>> depth;
vector<int> nodeDepth;
vector<int> futLeaves;
map<int,int> leaves;
bool dfs(int a,int prev,int cur){
if(cur>K){
return true;
}
if(cur==K){
leaves[a]=leaves.size();
}
bool found=false;
TRAV(i,adj[a]){
if(i!=prev){
bool val=dfs(i,a,cur+1);
if(val){
found=val;
futLeaves[a]=futLeaves[a] | futLeaves[i];
}
}
}
if(cur==K){
futLeaves[a]=(1<<a);
nodeDepth[a]=cur;
depth[cur].pb(a);
return true;
}
if(found){
depth[cur].pb(a);
nodeDepth[a]=cur;
}
return found;
}
string toBinary(int n, int len)
{
string binary;
for (unsigned i = (1 << len - 1); i > 0; i = i / 2) {
binary += (n & i) ? "1" : "0";
}
return binary;
}
int32_t main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>N>>K;
adj.resize(N+1);
futLeaves.resize(N+1);
nodeDepth.resize(N+1);
depth.resize(K+1);
FOR1(i,N){
futLeaves[i]=0;
nodeDepth[i]=-1;
}
FOR0(i,N-1){
int a,b;
cin>>a>>b;
adj[a].pb(b);
adj[b].pb(a);
}
if (K * K >= N) {
cout << "DA" << endl;
return 0;
}
dfs(1,-1,0);
// FOR1(i,N){
// cout<<i<<" : "<<toBinary(futLeaves[i],N)<<endl;
// }
// TRAV(i,leaves){
// cout<<i.first<<" "<<i.second<<endl;
// }
int dp[1<<(K)];
bool works=false;
FOR0(i,1<<(K)){
dp[i]=0;
FOR0(j,K+1){
if(i & (1<<j)){
TRAV(k,depth[j]){
//cout<<"AB: "<<j<<" "<<k<<endl;
int cur=futLeaves[k];
if(cur==0){continue;}
int first=N+2;
int last=-1;
for(int h=0;h<=N;h++){
if(cur & (1<<h)){
//cout<<"in: "<<h<<" "<<leaves[h]<<endl;
first=min(leaves[h],first);
break;
}
}
for(int h=N;h>=0;h--){
if(cur & (1<<h)){
last=max(leaves[h],last);
break;
}
}
TRAV(l,leaves){
if(l.second>=first && l.second<=last){
assert(cur & (1<<l.first));
}
}
assert(first!=(N+2));
assert(last!=(-1));
int bef=i & ~(1<<j);
if(first<=(dp[bef]+1)){
dp[i]=max(dp[i],last);
}
}
}
}
if(dp[i]==(depth[K].size()-1) && i!=1){
works=true;
}
}
// FOR0(i,1<<(K)){
// printBin(i,N);
// cout<<" "<<dp[i]<<endl;
// }
if(works){
cout<<"DA"<<endl;
}else{
cout<<"NE"<<endl;
}
return 0;
}
Compilation message
burza.cpp: In function 'std::string toBinary(int64_t, int64_t)':
burza.cpp:82:33: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
82 | for (unsigned i = (1 << len - 1); i > 0; i = i / 2) {
| ~~~~^~~
burza.cpp: In function 'int32_t main()':
burza.cpp:159:11: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
159 | if(dp[i]==(depth[K].size()-1) && i!=1){
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
724 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
2644 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
2644 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
1056 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
2644 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
2644 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
2644 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
980 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
828 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
1620 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
