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<iostream>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<tuple>
#include<set>
#include<map>
#include<random>
#include<chrono>
using namespace std;
const int MAX_N=4e2+2;
const int MASK=19;
int dp[(1<<MASK)];
int depth[MAX_N];
int in[MAX_N];
int out[MAX_N];
int T;
vector<int>nodes[MAX_N];
vector<int>g[MAX_N];
int n;
int k;
void dfs(int u,int par)
{
if(depth[u]==k)
{
in[u]=++T;
out[u]=T;
return;
}
in[u]=1e9;
for(int v:g[u])
{
if(v==par)continue;
depth[v]=depth[u]+1;
nodes[depth[v]].push_back(v);
dfs(v,u);
in[u]=min(in[u],in[v]);
out[u]=max(out[u],out[v]);
}
}
signed main ()
{
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>k;
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
if(k*k>=n)
{
cout<<"DA\n";
return 0;
}
dfs(1,0);
for(int mask=1;mask<(1<<k);mask++)
{
for(int ndepth=1;ndepth<=k;ndepth++)
{
if(((1<<(ndepth-1))&(mask))!=0)
{
for(int u:nodes[ndepth])
{
if(in[u]<=dp[mask & (~(1<<(ndepth-1)))]+1)
{
dp[mask]=max(dp[mask],out[u]);
}
}
}
}
if(dp[mask]==T)
{
cout<<"DA\n";
return 0;
}
}
cout<<"NE\n";
return 0;
}
# | 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... |