#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<vector<int>> cutoff_cover;
vector<pii> intervals;
map<int,int> lost;
bool dfs(int a,int prev,int cur){
if(cur>K){
return true;
}
if(cur==K){
cutoff_cover[a]={a};
lost[a]=lost.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];
cutoff_cover[a].insert(cutoff_cover[a].end(),cutoff_cover[i].begin(),cutoff_cover[i].end());
}
}
}
if(cur==K){
//futLeaves[a]=(1<<a);
depth[cur].pb(a);
return true;
}
if(found){
if(cur>=0){
depth[cur].pb(a);
}
}
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;
}
int max(int a, int b){
if(a>b){
return a;
}
return b;
}
int32_t main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>N>>K;
adj.resize(N);
// futLeaves.resize(N+1);
depth.resize(K+1);
cutoff_cover.resize(N);
FOR0(i,N-1){
int a,b;
cin>>a>>b;
a--;
b--;
adj[a].pb(b);
adj[b].pb(a);
}
assert(0==0);
if ((K * K) >= N) {
cout << "DA" << endl;
return 0;
}
//cout<<"cp2"<<endl;
//return 0;
dfs(0,-1,-1);
//return 0;
// intervals.pb({-1,-1});
TRAV(i,cutoff_cover){
if(i.empty()){
intervals.pb({-1,-1});
}else{
intervals.pb({lost[i[0]],lost[i.back()]});
}
}
// FOR1(i,N){
// cout<<i<<" : "<<toBinary(futLeaves[i],N)<<endl;
// }
// TRAV(i,leaves){
// cout<<i.first<<" "<<i.second<<endl;
// }
int dp[1<<(K)];
//cout<<"cp1"<<endl;
//return 0;
bool works=false;
FOR0(i,1<<K){
if(i==0){dp[i]=0; continue;}
dp[i]=0;
FOR0(j,K){
if(i & (1<<j)){
TRAV(l,depth[i]){
//assert(l<intervals.size());
//int first=intervals[l].first;
//int last=intervals[l].second;
if(intervals[l].first<=(dp[i & ~(1<<j)]+1)){
dp[i]=max(dp[i],intervals[l].second);
}
}
}
}
if(dp[i]==(depth[K].size()-1)){
works=true;
}
//return 0;
}
// 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:85:33: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
85 | for (unsigned i = (1 << len - 1); i > 0; i = i / 2) {
| ~~~~^~~
burza.cpp: In function 'int32_t main()':
burza.cpp:161: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]
161 | if(dp[i]==(depth[K].size()-1)){
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
724 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
2644 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
2516 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
980 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
2516 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
2516 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
2516 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
980 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
724 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
1492 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
