//https://oj.uz/problem/view/COCI16_burza
#include <bits/stdc++.h>
using namespace std;
using lli = int64_t;
const int MAX_N = 400 + 5;
int dp[MAX_N][MAX_N][2];
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, k; cin >> n >> k;
vector <vector <int>> graph(n + 1);
for (int i = 1; i < n; ++i) {
int u, v; cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
vector <int> parent(n + 1);
auto DFS = [&] (auto DFS, int u) -> void {
int leaf = true;
for (int v : graph[u]) {
if (v == parent[u]) continue;
parent[v] = u;
leaf = false;
DFS(DFS, v);
}
if (leaf) {
for (int i = 1; i <= k; ++i) dp[u][i][1] = true;
dp[u][0][0] = true;
return;
}
for (int plays = 0; plays <= k; ++plays) {
for (int turn : {0, 1}) {
if (plays < turn) continue;
for (int v : graph[u]) {
if (v == parent[u]) continue;
int current = true;
for (int t : graph[u]) {
if (v == t or v == parent[u]) continue;
current &= not dp[v][plays - turn][turn ^ 1];
}
dp[u][plays][turn] |= current;
}
}
}
// cerr << "DEBUG: " << u << '\n';
// for (int plays = 0; plays <= k; ++plays) cerr << dp[u][plays][0] << ' ' << dp[u][plays][1] << '\n';
};
DFS(DFS, 1);
int ans = dp[1][k][1];
cout << (ans ? "DA" : "NE");
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
1368 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
1628 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
1628 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
1624 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
1628 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
1624 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
1628 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
1624 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
1116 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
1372 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |