Submission #394252

#	Time	Username	Problem	Language	Result	Execution time	Memory
394252		ParsaPordastan	Burza (COCI16_burza)	C++14	160 / 160	81 ms	10592 KiB

burza

#include <bits/stdc++.h>
using namespace std;

const int N = 4 * 100 + 1;
const int LG = 20;

int n, k, st[N], en[N], h[N];
int TM;
int dp[N][1 << LG];
vector <int> adj[N], chk[N];

void DFS(int v, int par) {
	if (h[v] == k - 1) {
		st[v] = TM++;
		en[v] = TM;
		return;
	}
	st[v] = TM;
	for (auto u: adj[v])
		if (u != par) {
			h[u] = h[v] + 1;
			DFS(u, v);
		}
	en[v] = TM;
}

int main() { 
	ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	cin >> n >> k;
	if (k * k >= n)
		return cout << "DA\n", 0;
	for (int i = 1, v, u; i < n; i++) {
		cin >> v >> u;
		adj[v].push_back(u);
		adj[u].push_back(v);
	}
	h[1] = -1;
	DFS(1, 0);
	//cout << TM << '\n';
	for (int i = 2; i <= n; i++)
		chk[st[i]].push_back(i);
	dp[0][0] = 1;
	for (int i = 0; i < TM; i++)
		for (int mask = 0; mask < (1 << k); mask++) {
			if (!dp[i][mask])
				continue;
			for (auto v: chk[i]) {
				if (mask >> h[v] & 1);
				else {
					//cout << "KHAR\n" << en[v] << ' ' << mask << '\n';
					dp[en[v]][mask + (1 << h[v])] = 1;
				}
			}
		}
	for (int mask = 0; mask < (1 << k); mask++)
		if (dp[TM][mask]) {
			//cout << TM << " " << mask << endl;
			return cout << "DA\n", 0;
		}
	cout << "NE" << '\n';
	return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 16 / 16
• Subtask 8: 16 / 16
• Subtask 9: 16 / 16
• Subtask 10: 16 / 16