#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N, K;
int best[401][401]; // cant mark node till xth turn
int dp[1 << 21];
vector<int> adj[401];
int depth[401];
void dfs(int node, int p, int d)
{
vector<int> paths;
for (int i : adj[node])
{
if (i == p)
continue;
dfs(i, node, d + 1);
depth[node] = max(depth[node], depth[i]);
if (depth[i] >= K)
paths.push_back(i);
}
int n = paths.size();
for (int move = 1; move <= K; ++move) // start marking till move'th move
{
if (move <= d)
best[node][move] = 1;
else if (n > K)
best[node][move] = 1e9;
else
{
for (int mask = 1; mask < (1 << n); ++mask)
{
dp[mask] = 1e9;
for (int i = 0; i < n; ++i)
if (mask & (1 << i))
{
int cur_move = move + dp[mask ^ (1 << i)];
if (cur_move > K) // not possible
continue;
dp[mask] = min(dp[mask], dp[mask ^ (1 << i)] + best[paths[i]][cur_move]);
}
}
best[node][move] = dp[(1 << n) - 1];
}
}
depth[node] = max(depth[node], d);
}
int main()
{
cin.tie(NULL) -> sync_with_stdio(false);
cin >> N >> K;
for (int i = 1; i < N; ++i)
{
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(1, 0, 0);
cout << (best[1][1] <= K ? "DA" : "NE") << endl;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
848 KB |
Output is correct |
2 |
Correct |
117 ms |
1616 KB |
Output is correct |
3 |
Correct |
295 ms |
9288 KB |
Output is correct |
4 |
Runtime error |
157 ms |
18504 KB |
Execution killed with signal 11 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
119 ms |
1360 KB |
Output is correct |
2 |
Correct |
117 ms |
1360 KB |
Output is correct |
3 |
Correct |
19 ms |
2128 KB |
Output is correct |
4 |
Correct |
71 ms |
5148 KB |
Output is correct |
5 |
Correct |
117 ms |
1612 KB |
Output is correct |
6 |
Correct |
1 ms |
1104 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
117 ms |
1360 KB |
Output is correct |
2 |
Correct |
116 ms |
1360 KB |
Output is correct |
3 |
Correct |
57 ms |
3040 KB |
Output is correct |
4 |
Correct |
166 ms |
9200 KB |
Output is correct |
5 |
Correct |
1 ms |
848 KB |
Output is correct |
6 |
Correct |
1 ms |
592 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
28 ms |
1276 KB |
Output is correct |
2 |
Correct |
119 ms |
1616 KB |
Output is correct |
3 |
Correct |
23 ms |
2128 KB |
Output is correct |
4 |
Runtime error |
165 ms |
18504 KB |
Execution killed with signal 11 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
116 ms |
1360 KB |
Output is correct |
2 |
Correct |
120 ms |
1360 KB |
Output is correct |
3 |
Runtime error |
190 ms |
18504 KB |
Execution killed with signal 11 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
116 ms |
1616 KB |
Output is correct |
2 |
Correct |
120 ms |
1360 KB |
Output is correct |
3 |
Correct |
10 ms |
1784 KB |
Output is correct |
4 |
Runtime error |
174 ms |
18448 KB |
Execution killed with signal 11 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
119 ms |
1616 KB |
Output is correct |
2 |
Correct |
117 ms |
1360 KB |
Output is correct |
3 |
Runtime error |
163 ms |
18472 KB |
Execution killed with signal 11 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
1104 KB |
Output is correct |
2 |
Correct |
117 ms |
1628 KB |
Output is correct |
3 |
Correct |
36 ms |
3144 KB |
Output is correct |
4 |
Runtime error |
198 ms |
18396 KB |
Execution killed with signal 11 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
1016 KB |
Output is correct |
2 |
Correct |
119 ms |
1616 KB |
Output is correct |
3 |
Correct |
26 ms |
2088 KB |
Output is correct |
4 |
Runtime error |
157 ms |
18504 KB |
Execution killed with signal 11 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
54 ms |
1104 KB |
Output is correct |
2 |
Correct |
117 ms |
1616 KB |
Output is correct |
3 |
Correct |
33 ms |
3140 KB |
Output is correct |
4 |
Correct |
20 ms |
1936 KB |
Output is correct |
5 |
Correct |
54 ms |
1104 KB |
Output is correct |
6 |
Correct |
1 ms |
760 KB |
Output is correct |