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 <vector>
using namespace std;
int n, k;
vector <vector <int>> adj;
vector <int> depth;
const int maxn = 400 + 1;
bool dp[maxn][maxn];
bool ready[maxn][maxn];
void get_depth(int s, int p, int d) {
depth[s] = d;
if (d == k) {
ready[s][d] = true;
dp[s][d] = false;
return;
}
if (adj[s].size() == 1 && s != p) {
// if we reach this node, then we can win
ready[s][d] = true;
dp[s][d] = true;
return;
}
for (auto i : adj[s]) {
if (i == p)
continue;
get_depth(i, p, d+1);
}
}
bool solve(int s, int p) {
if (ready[s][depth[s]])
return dp[s][depth[s]];
int false_dps = 0;
int true_dps = 0;
for (auto i : adj[s]) {
if (i == p)
continue;
if (solve(i, s))
true_dps++;
else
false_dps++;
}
if (true_dps > 0)
return true;
else if (false_dps == 1)
return true;
return false;
}
int main() {
cin >> n >> k;
adj.resize(n+1);
depth.resize(n+1);
for (int i = 0; i < n-1; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
get_depth(1, 1, 0);
if (solve(1, 1))
cout << "DA\n";
else
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... |