Submission #398301

#	Time	Username	Problem	Language	Result	Execution time	Memory
398301		Mwhdi	Burza (COCI16_burza)	C++14	48 / 160	2 ms	460 KiB

burza

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

#define F first
#define S second

const int maxn = 4e2+10;
int n, k, H[maxn], MAX_H[maxn], cost[maxn], dad[maxn];
set <int> G[maxn];
bool visited[maxn], ANS[maxn];

void dfs (int v , int h) {
	visited[v] = 1;
	H[v] = h;
	if (H[v] == k) {
		ANS[v] = 1;	
	}
	MAX_H[v] = h;
	for (int i : G[v]) {
		if (!visited[i]) {
			dad[i] = v;
			dfs (i , h+1);
			MAX_H[v] = max (MAX_H[v] , MAX_H[i]);
		}
	}
}

void solve (int v) {
	visited[v] = 1;
	if (ANS[v]) {
		return ;
	}
	for (int i : G[v]) {
		if (!visited[i]) {
			solve (i);
		}
	}
	set <int> vertices, nei;
	vertices.insert (v);
	for (int t = 1; t <= k - H[v]; t++) {
		for (int vertex : vertices) {
			for (int i : G[vertex]) {
				if (i != dad[vertex]) {
					nei.insert (i);
				}
			}
		}
		vertices.clear ();
		for (int i : nei) {
			vertices.insert (i);
		}
		nei.clear ();
		int MAX_cost = -1, erase_v = 0;
		for (int i : vertices) {
			if (cost[i] > MAX_cost) {
				MAX_cost = cost[i];
				erase_v = i;
			}
		}
		vertices.erase (vertices.find(erase_v));
		if (!vertices.size()) {
			cost[v] = t;
			return ;
		}
	}
	if (vertices.size()) {
		cost[v] = 1e9;
	}
	ANS[v] = 1;
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> k;
	for (int i = 1; i <= n-1; i++) {
		int u, v; cin >> u >> v;
		G[u].insert (v);
		G[v].insert (u);
	}
	dfs (1 , 0);
	bool ans = 1;
	for (int i = 1; i <= n; i++) {
		if (MAX_H[i] < k || H[i] > k) {
			for (int j = 1; j <= n; j++) {
				if (G[j].find (i) != G[j].end()) {
					G[j].erase (G[j].find (i));
				}
			}
		}
		else {
			ans = 0;
		}
	}
	if (ans) {
		cout << "DA";
		return 0;
	}
	for (int i = 1; i <= n; i++) {
		visited[i] = 0;
	}
	solve (1);
	if (cost[1] == 1e9) {
		cout << "NE";
	}
	else {
		cout << "DA";
	}
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 16
• Subtask 7: 0 / 16
• Subtask 8: 16 / 16
• Subtask 9: 0 / 16
• Subtask 10: 0 / 16