Submission #727043

#	Time	Username	Problem	Language	Result	Execution time	Memory
727043		beaboss	Burza (COCI16_burza)	C++14	160 / 160	493 ms	972 KiB

burza

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<ll, ll> pii;

const int maxn = 401;

int depth[maxn];
vector<int> adj[maxn];

vector<int> newadj[maxn];

void findD(int cur, int d, int p) {
	depth[cur]=d;
	for (auto val: adj[cur]) {
		if (val != p) findD(val, d+ 1, cur);
	}
}
bool v[maxn];

void createTree(int cur) {
	if (v[cur]) return;
	v[cur]=true;
	for (auto val: adj[cur]) {
		// assert(cur != val);
		if (depth[val] == depth[cur]-1) {
			// cout << cur << val << endl;
			newadj[cur].pb(val);
			newadj[val].pb(cur);
			createTree(val);
		}
	}
}

int leafcounter = -1;

pair<int, int> ranges[maxn];

pair<int, int> assignRange(int cur, int p) {
	if (newadj[cur].size() == 1) {
		leafcounter++;
		ranges[cur] = {leafcounter, leafcounter};
		return {leafcounter, leafcounter};
	}
	pair<int, int> rval = {10000000, -1};
	for (auto val: newadj[cur]) {
		if (val != p) {
			auto cval = assignRange(val, cur);
			rval.f = min(rval.f, cval.f);
			rval.s = max(rval.s, cval.s);
		}
	}

	ranges[cur] = rval;
	return rval;


}

int main() {
	
	int  n, k;
	cin >> n >> k;

	if (k * k > n) {
		cout << "DA" << endl;
		return 0;
	}

	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);
	}

	findD(0, -1, -1);

	for (int i = 0; i < n; i++) {
		if (depth[i] == k-1) {
			createTree(i);
		}
	}

	assignRange(0, -1);

	
	vector<int> dp((1 << k), -1);
	dp[0] = 0;

	for (int i = 0; i < (1 << k); i++) {
		for (int j = 0; j < k; j++) {
			if ((1 << j) & i) {
				int curdp = 0;
				for (int nxt = 0; nxt < n;nxt++) {
					if (depth[nxt] == j && ranges[nxt].f <= dp[i ^ (1 << j)]) {
						curdp = max(curdp, ranges[nxt].s + 1);
					}
				}
				dp[i] = max(dp[i], curdp);
			}
		}
		if (dp[i] == leafcounter + 1) {
			cout << "DA" << endl;
			return 0;
		}
	}
	cout << "NE" << endl;

	



	
	
}

• 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