Submission #229260

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
229260	2020-05-04T00:00:42 Z	MetB	Burza (COCI16_burza)	C++14	160 / 160	213 ms	25208 KB

burza

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
 
#define N 1000003
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e6 + 3;

int n, k, ptr;
bitset <1 << 21> d[401];

vector <int> g[N];
vector < pair <int, int> > v[401];

void dfs (int x, int p, int h) {
	if (h == k) {
		v[++ptr].push_back ({ptr, h - 1});
		return;
	}

	int l = ptr + 1;

	for (int to : g[x])
		if (to != p) dfs (to, x, h + 1);
	int r = ptr;
	if (h && l) v[r].push_back ({l, h - 1});
}

int main () {
	cin >> n >> k;

	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		g[a].push_back (b);
		g[b].push_back (a);
	}

	if (k * k >= n) {
		cout << "DA";
		return 0;
	}

	dfs (0, -1, 0);

	d[0][0] = 1;
	for (int i = 1; i <= ptr; i++) {
		for (int j = 1; j < (1 << k); j++) {
			for (auto a : v[i]) {
				if (j & (1 << a.second)) {
					d[i][j] = (d[i][j] | d[a.first - 1][j - (1 << a.second)]);
				}
			}

			if (ptr == i && d[i][j]) {
				cout << "DA";
				return 0;
			}
		}
	}

	cout << "NE";
}

Subtask #1
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	24568 KB	Output is correct
2	Correct	211 ms	25184 KB	Output is correct
3	Correct	18 ms	23808 KB	Output is correct
4	Correct	17 ms	23808 KB	Output is correct
5	Correct	19 ms	24960 KB	Output is correct
6	Correct	22 ms	24064 KB	Output is correct

Subtask #2
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	203 ms	25000 KB	Output is correct
2	Correct	200 ms	24952 KB	Output is correct
3	Correct	18 ms	23808 KB	Output is correct
4	Correct	19 ms	23808 KB	Output is correct
5	Correct	211 ms	24972 KB	Output is correct
6	Correct	19 ms	25088 KB	Output is correct

Subtask #3
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	208 ms	24956 KB	Output is correct
2	Correct	207 ms	24952 KB	Output is correct
3	Correct	18 ms	23808 KB	Output is correct
4	Correct	18 ms	23808 KB	Output is correct
5	Correct	20 ms	24576 KB	Output is correct
6	Correct	18 ms	23936 KB	Output is correct

Subtask #4
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	65 ms	24440 KB	Output is correct
2	Correct	211 ms	25208 KB	Output is correct
3	Correct	18 ms	23808 KB	Output is correct
4	Correct	19 ms	23808 KB	Output is correct
5	Correct	18 ms	24448 KB	Output is correct
6	Correct	18 ms	23936 KB	Output is correct

Subtask #5
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	196 ms	24824 KB	Output is correct
2	Correct	206 ms	25084 KB	Output is correct
3	Correct	18 ms	23808 KB	Output is correct
4	Correct	18 ms	23808 KB	Output is correct
5	Correct	19 ms	24832 KB	Output is correct
6	Correct	18 ms	24576 KB	Output is correct

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	202 ms	24996 KB	Output is correct
2	Correct	198 ms	24952 KB	Output is correct
3	Correct	18 ms	23808 KB	Output is correct
4	Correct	18 ms	23808 KB	Output is correct
5	Correct	19 ms	24960 KB	Output is correct
6	Correct	18 ms	24448 KB	Output is correct

Subtask #7
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	212 ms	25080 KB	Output is correct
2	Correct	201 ms	24952 KB	Output is correct
3	Correct	18 ms	23808 KB	Output is correct
4	Correct	18 ms	23808 KB	Output is correct
5	Correct	213 ms	24952 KB	Output is correct
6	Correct	18 ms	24576 KB	Output is correct

Subtask #8
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	61 ms	24364 KB	Output is correct
2	Correct	209 ms	25080 KB	Output is correct
3	Correct	19 ms	23808 KB	Output is correct
4	Correct	20 ms	23936 KB	Output is correct
5	Correct	18 ms	24448 KB	Output is correct
6	Correct	18 ms	24960 KB	Output is correct

Subtask #9
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	36 ms	24448 KB	Output is correct
2	Correct	213 ms	25080 KB	Output is correct
3	Correct	18 ms	23808 KB	Output is correct
4	Correct	19 ms	23808 KB	Output is correct
5	Correct	18 ms	24448 KB	Output is correct
6	Correct	19 ms	24704 KB	Output is correct

Subtask #10
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	102 ms	24356 KB	Output is correct
2	Correct	208 ms	25148 KB	Output is correct
3	Correct	18 ms	23808 KB	Output is correct
4	Correct	21 ms	23808 KB	Output is correct
5	Correct	103 ms	24444 KB	Output is correct
6	Correct	19 ms	24320 KB	Output is correct

Submission #229260

Compilation message