oj.uz

답안 #872349

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
872349 2023-11-12T23:52:25 Z vjudge1 Burza (COCI16_burza) C++14
0 / 160
 32 ms 50776 KB 
#include <bits/stdc++.h>
#define int long long
#define MOD 998244353
#define N 1010
using namespace std;
int n, k, dp[25][1500000], 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("NE");
		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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 30 ms 50516 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 31 ms 50572 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 29 ms 50424 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 32 ms 50776 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 28 ms 50524 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 30 ms 50516 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 29 ms 50524 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 29 ms 50524 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 29 ms 50392 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 29 ms 50504 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -