# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
926564 |
2024-02-13T09:46:01 Z |
MinaRagy06 |
Burza (COCI16_burza) |
C++17 |
|
1000 ms |
524288 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 405;
vector<int> adj[N];
int par[N], dep[N], t;
array<int, 2> v[N];
int n, k;
vector<int> gud[N];
void dfs(int i, int p, int d) {
for (auto nxt : adj[i]) {
if (nxt == p) continue;
dfs(nxt, i, d + 1);
v[i][0] = min(v[i][0], v[nxt][0]);
v[i][1] = max(v[i][1], v[nxt][1]);
}
dep[i] = d;
if (d == k) {
v[i][0] = min(v[i][0], t);
v[i][1] = max(v[i][1], t);
t++;
}
if (v[i][0] != n + 1) {
par[i] = p;
gud[d].push_back(i);
}
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> k;
if (n <= k * (k + 1) / 2) {
cout << "DA\n";
return 0;
}
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
v[i] = {n + 1, -1};
}
dfs(1, 0, 0);
for (int i = 1; i <= n; i++) adj[i].clear();
for (int i = 1; i <= n; i++) {
if (!par[i]) continue;
adj[par[i]].push_back(i);
}
// for (int i = 1; i <= k; i++) {
// for (auto j : gud[i]) {
// cout << v[j][0] << ", " << v[j][1] << '\n';
// }
// cout << '\n';
// }
int m = 1 << k, dp[m];
dp[0] = -1;
for (int msk = 1; msk < m; msk++) {
dp[msk] = -1;
for (int j = 1; j <= k; j++) {
if (!((msk >> (j - 1)) & 1)) continue;
for (auto i : gud[j]) {
if (v[i][0] <= dp[msk ^ (1 << (j - 1))] + 1) {
dp[msk] = max(dp[msk], v[i][1]);
}
}
}
}
if (dp[m - 1] == t - 1) {
cout << "DA\n";
} else {
cout << "NE\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
348 KB |
Output is correct |
2 |
Correct |
33 ms |
860 KB |
Output is correct |
3 |
Execution timed out |
1097 ms |
131708 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
856 KB |
Output is correct |
2 |
Correct |
32 ms |
856 KB |
Output is correct |
3 |
Execution timed out |
1092 ms |
262980 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
860 KB |
Output is correct |
2 |
Correct |
32 ms |
860 KB |
Output is correct |
3 |
Execution timed out |
1090 ms |
262960 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
604 KB |
Output is correct |
2 |
Correct |
34 ms |
860 KB |
Output is correct |
3 |
Runtime error |
286 ms |
524288 KB |
Execution killed with signal 9 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
988 KB |
Output is correct |
2 |
Correct |
31 ms |
856 KB |
Output is correct |
3 |
Execution timed out |
1059 ms |
131668 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
856 KB |
Output is correct |
2 |
Correct |
31 ms |
860 KB |
Output is correct |
3 |
Execution timed out |
1091 ms |
263212 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
860 KB |
Output is correct |
2 |
Correct |
31 ms |
1008 KB |
Output is correct |
3 |
Runtime error |
260 ms |
524288 KB |
Execution killed with signal 9 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
604 KB |
Output is correct |
2 |
Correct |
32 ms |
860 KB |
Output is correct |
3 |
Execution timed out |
1079 ms |
262996 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
348 KB |
Output is correct |
2 |
Correct |
33 ms |
984 KB |
Output is correct |
3 |
Execution timed out |
1036 ms |
262884 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
748 KB |
Output is correct |
2 |
Correct |
32 ms |
1112 KB |
Output is correct |
3 |
Execution timed out |
1083 ms |
131736 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |