Submission #520861

#	Time	Username	Problem	Language	Result	Execution time	Memory
520861		Cantfindme	Burza (COCI16_burza)	C++17	160 / 160	11 ms	1376 KiB

burza

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end() 

const int maxn = 410;
const int mod = 1e9+7; 

typedef long double ld;
const ld INF = 10005;

int n, K;
vector <int> adjlist[maxn];
int best[maxn][21];
int dp[1 << 20];

int co = 0;

void dfs(int x, int d, int p) {
	if (d == K - 1) {
		best[co][K-1] = co+1;
		co++;
		return;
	}
	
	int pref = co;
	
	for (auto i: adjlist[x]) if (i != p) {
		dfs(i, d + 1, x);
	}
	
	int post = co;
	for (int i = pref; i < post; i++) {
		best[i][d] = post;
	}
}

int32_t main() {
	FAST
	cin >> n >> K;
	for (int i =0;i<n-1;i++) {
		int a,b; cin >> a >> b;
		adjlist[a].push_back(b);
		adjlist[b].push_back(a);
	}
	
	if (n - 1 < K * (K+1)) {
		cout << "DA";
		return 0;
	}
	
	dfs(1, -1, -1); //node 1 is depth -1 so that its children are depth 0
	
	
	for (int bm = 1; bm < (1 << K); bm++) {
		int res = 0;
		for (int d = 0; d < K; d++) {
			if (~bm & (1 << d)) continue;
			res = max(res, best[dp[bm ^ (1 << d)]][d]);
		}
		dp[bm] = res;
		if (res == co) {
			cout << "DA";
			return 0;
		}
	}
	cout << "NE";
}

• 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