# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
243443 |
2020-07-01T07:43:20 Z |
NONAME |
Burza (COCI16_burza) |
C++14 |
|
273 ms |
39544 KB |
#include <bits/stdc++.h>
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie()
using namespace std;
using ll = long long;
int n, k;
bool f[1 << 21], nf[1 << 21], st[25][1 << 21], mk[1 << 21];
vector <int> g[500];
void dfs1(int v, int pr = -1, int d = -1) {
if (d == k - 1) {
mk[v] = 1;
return;
}
for (int u : g[v])
if (u != pr)
dfs1(u, v, d + 1), mk[v] |= mk[u];
}
void dfs2(int v, int pr = 0, int d = -1) {
if (!mk[v])
return;
if (v)
memcpy(st[d], f, sizeof(f));
for (int u : g[v])
if (u != pr)
dfs2(u, v, d + 1);
if (!v)
return;
memset(nf, 0, sizeof(nf));
for (int i = 0; i < (1 << k); ++i)
if (d == k - 1) {
if (!(i & (1 << d)))
nf[i | (1 << d)] |= f[i];
} else {
nf[i] |= f[i];
if (!(i & (1 << d)))
nf[i | (1 << d)] |= st[d][i];
}
memcpy(f, nf, sizeof(nf));
}
int main() {
fast_io;
cin >> n >> k;
for (int i = 0; i < n - 1; ++i) {
int v, u;
cin >> v >> u;
--v, --u;
g[v].push_back(u);
g[u].push_back(v);
}
dfs1(0);
if (k * k >= n || !mk[0]) {
cout << "DA\n";
return 0;
}
f[0] = 1;
dfs2(0);
for (int msk = 0; msk < (1 << k); ++msk)
if (f[msk]) {
cout << "DA\n";
return 0;
}
cout << "NE\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
142 ms |
33280 KB |
Output is correct |
2 |
Correct |
235 ms |
39416 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
184 ms |
18936 KB |
Output is correct |
6 |
Correct |
43 ms |
14720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
235 ms |
39416 KB |
Output is correct |
2 |
Correct |
227 ms |
39416 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
228 ms |
39416 KB |
Output is correct |
6 |
Correct |
158 ms |
16768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
230 ms |
39544 KB |
Output is correct |
2 |
Correct |
259 ms |
39544 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
126 ms |
18816 KB |
Output is correct |
6 |
Correct |
43 ms |
14720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
192 ms |
35192 KB |
Output is correct |
2 |
Correct |
267 ms |
39416 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
109 ms |
16768 KB |
Output is correct |
6 |
Correct |
38 ms |
14840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
232 ms |
39416 KB |
Output is correct |
2 |
Correct |
246 ms |
39416 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
153 ms |
18816 KB |
Output is correct |
6 |
Correct |
111 ms |
16768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
247 ms |
39544 KB |
Output is correct |
2 |
Correct |
227 ms |
39424 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
138 ms |
14840 KB |
Output is correct |
6 |
Correct |
123 ms |
16768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
273 ms |
39544 KB |
Output is correct |
2 |
Correct |
243 ms |
39416 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
228 ms |
39424 KB |
Output is correct |
6 |
Correct |
160 ms |
18936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
165 ms |
35192 KB |
Output is correct |
2 |
Correct |
232 ms |
39416 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
109 ms |
16888 KB |
Output is correct |
6 |
Correct |
157 ms |
16768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
130 ms |
33272 KB |
Output is correct |
2 |
Correct |
264 ms |
39504 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
98 ms |
16768 KB |
Output is correct |
6 |
Correct |
170 ms |
20864 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
175 ms |
37368 KB |
Output is correct |
2 |
Correct |
246 ms |
39416 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
189 ms |
37368 KB |
Output is correct |
6 |
Correct |
73 ms |
14720 KB |
Output is correct |