Submission #1036761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036761		ef10	Burza (COCI16_burza)	C++17	160 / 160	44 ms	976 KiB

burza

// Source: https://usaco.guide/general/io

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

int N, K;
vector<int> dn[401];
vector<int> adj[401];
map<int,int> leaf;
vector<int> cover[401];
pair<int,int> interval[401];
int dp[1<<20];

void dfs(int c, int p, int d) {
	dn[d].push_back(c);
	if (d == K) {
		leaf[c]=leaf.size();
		cover[c].push_back(c);
		return;
	}
	for (auto n : adj[c]) {
		if (n==p) continue;
		dfs(n,c,d+1);
		for (auto l : cover[n]) {
			cover[c].push_back(l);
		}
	}
}

int main() {
	cin >> N >> K;
	for (int i = 0; i < N-1; i++) {
		int a,b; cin >> a >> b;
		a--;b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	if (K*K>N) {
		cout << "DA" << endl;
		return 0;
	}
	dfs(0,0,0);
	/*cout << "cover" << endl;
	for (int i = 0; i < N; i++) {
		cout << i << ": ";
		for (auto n : cover[i]) {
			cout << n << " ";
		}
		cout << endl;
	}
	cout << "leaf" << endl;
	for (auto e : leaf) {
		cout << e.first << "/" << e.second << endl;
	}
	cout << "dn" << endl;
	for (int i =0; i <= K; i++) {
		cout << i << ": ";
		for (auto e : dn[i]) {
			cout << e << " ";
		}
		cout << endl;
	}*/
	for (int i = 0; i < N; i++) {
		if (cover[i].size()== 0) {
			interval[i]=make_pair(-1,-1);
			continue;
		}
		interval[i]=make_pair(leaf[cover[i][0]],leaf[cover[i][cover[i].size()-1]]);
	}
	/*cout << "interval" << endl;
	for (int i = 0; i < N; i++) {
		cout << i << "/" << interval[i].first << "/" << interval[i].second << endl;
	}*/
	for (int i = 0; i < (1<<K); i++) {
		for (int j = 0; j < K; j++) {
			if (!(i & (1<<j))) continue;
			int prev = dp[i & ~(1<<j)];
			for (auto o : dn[j+1]) {
				if (interval[o].first <= prev) {
					dp[i] = max(dp[i],interval[o].second+1);
				}
			}
		}
		//cout << "dp["<<i<<"] = " << dp[i] << endl;
		if (dp[i] == leaf.size()) {
			cout << "DA" << endl;
			return 0;
		}
	}
	cout << "NE" << endl;
}

Compilation message (stderr)

burza.cpp: In function 'int main()':
burza.cpp:85:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |   if (dp[i] == leaf.size()) {
      |       ~~~~~~^~~~~~~~~~~~~~

• 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