oj.uz

Submission #872351

# Submission time Handle Problem Language Result Execution time Memory
872351 2023-11-12T23:54:52 Z vjudge1 Burza (COCI16_burza) C++14
0 / 160
 270 ms 27304 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 3676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 270 ms 26108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 216 ms 27304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 8796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 178 ms 25944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 226 ms 27288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 240 ms 27228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 6744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 3672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 14992 KB Output isn't correct
2 Halted 0 ms 0 KB -