Submission #872351

#	Time	Username	Problem	Language	Result	Execution time	Memory
872351		vjudge1	Burza (COCI16_burza)	C++14	0 / 160	270 ms	27304 KiB

burza

#include <bits/stdc++.h>
#define int long long
#define MOD 998244353
#define N 1010
using namespace std;
int n, k, dp[1500000][25], u, v, dfn[410], dfnt, dfnrngl[410], dfnrngr[410], dep[410], dq[410], dqt, idx[410];
vector<int> a[410];
template <typename T>
inline void read(T &t)
{
	t = 0;
	register char ch = getchar();
	while (!('0' <= ch && ch <= '9'))
	{
		if (ch == '-')
			t *= -1;
		ch = getchar();
	}
	while (('0' <= ch && ch <= '9'))
	{
		t = ((t << 1) + (t << 3)) + ch - '0';
		ch = getchar();
	}
}
void dfs(int nw, int fa)
{
	dep[nw] = dep[fa] + 1;
	if (dep[nw] == k + 1)
		dfn[nw] = ++dfnt;
	dq[nw] = ++dqt;
	idx[dqt] = nw;
	dfnrngl[nw] = dfn[nw] ? dfn[nw] : dfnt + 1;
	for (int v : a[nw])
		if (v != fa)
			dfs(v, nw);
	dfnrngr[nw] = dfnt;
}
#define checkmax(a, b) (a = max(a, (b)))
signed main()
{
	read(n);
	read(k);
	if (k > 19)
	{
		puts("DA");
		return 0;
	}
	for (int i = 1; i < n; i++)
	{
		read(u);
		read(v);
		a[u].emplace_back(v);
		a[v].emplace_back(u);
	}
	dfs(1, 0);
	dp[0][1] = 1;
	int rng = (1 << k);
	for (int i = 2; i <= n; i++)
		if (dep[idx[i]] <= k + 1)
			for (int j = 0; j < rng; j++)
				if (!(j & (1 << (dep[idx[i]] - 2))))
					dp[j | (1 << (dep[idx[i]] - 2))][dfnrngr[idx[i]] + 1] |= dp[j][dfnrngl[idx[i]]];
	for (int j = 0; j < rng; j++)
		if (dp[j][dfnt + 1])
		{
			puts("DA");
			return 0;
		}
	puts("NE");
	return 0;
}

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