This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//Some wierd BFS can also pass(?)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define siz(x) (int)x.size()
#define pb push_back
#define all(x) x.begin(), x.end()
//===========================================
const int MAX = 405;
vi adj[MAX];
int p[MAX], dep[MAX], depb[MAX];
set<vi> vis;
void dfs(int v){
for (int u: adj[v]){
if (u == p[v]) continue;
p[u] = v;
dep[u] = dep[v]+1;
dfs(u);
depb[v] = max(depb[v], depb[u]+1);
}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
int n, k; cin >> n >> k;
for (int i = 1; i < n; i++){
int a, b; cin >> a >> b;
adj[a].pb(b);
adj[b].pb(a);
}
dfs(1);
queue<vi> q; q.push({1});
while (siz(q)){
auto vec = q.front(); q.pop();
if (vec.empty()){
cout << "DA\n";
return 0;
}
int rem = k-dep[vec[0]];
vi vv;
for (int v: vec){
for (int u: adj[v]){
if (u == p[v]) continue;
if (depb[u]+1 >= rem) vv.pb(u);
}
}
if (siz(vv) > rem) continue;
for (int i = 0; i < siz(vv); i++){
swap(vv[i], vv.back());
vector<int> temp = vv; temp.pop_back();
if (!vis.count(temp)){
q.push(temp);
vis.insert(temp);
}
swap(vv[i], vv.back());
}
}
cout << "NE\n";
}
# | 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... |