This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 400;
int depth[MAX_N];
int occ[MAX_N];
int n,k;
vector<vector<int>> adj;
vector<vector<int>> ch;
void dfs(int u, int anc, int dpth){
for(auto v:adj[u]){
if(v!=anc){
ch[u].push_back(v);
dfs(v, u, dpth+1);
}
}
depth[u] = dpth;
occ[dpth]++;
}
vector<bitset<30>> dp(int u){
vector<bitset<30>> cur;
vector<bitset<30>> new_cur;
if(depth[u]!=k){
if(ch[u].size()>0){
new_cur.push_back(bitset<30>(0));
for(auto v: ch[u]){
swap(cur, new_cur);
vector<bitset<30>> child_dp = dp(v);
for(auto e: cur){
for(auto f: child_dp){
if((e&f).none()){
new_cur.push_back(e|f);
}
}
}
cur.clear();
}
bitset<30> other;
other[depth[u]] = true;
new_cur.push_back(other);
}
else{
new_cur.push_back(bitset<30>(0));
}
}
else{
bitset<30> other;
other[depth[u]] = true;
new_cur.push_back(other);
}
/*cout<<u<<endl;
for(auto e: new_cur){
cout<<e<<endl;
}*/
return new_cur;
}
signed main(){
cin>>n>>k;
adj.resize(n);
ch.resize(n);
for(int i =0; i<n-1; i++){
int a, b;
cin>>a>>b;
a--;
b--;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(0, -1, 0);
for(int i = 1; i<k; i++){
if(occ[i]-1<i){
cout<<"NE"<<endl;
return 0;
}
}
auto res = dp(0);
for(auto e: res){
if(e[0] == false){
cout<<"DA"<<endl;
return 0;
}
else{
cout<<"NE"<<endl;
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |