oj.uz

Submission #398301

# Submission time Handle Problem Language Result Execution time Memory
398301 2021-05-04T06:43:44 Z Mwhdi Burza (COCI16_burza) C++14
48 / 160
 2 ms 460 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 1 ms 344 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Incorrect 1 ms 332 KB Output isn't correct

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Incorrect 1 ms 460 KB Output isn't correct

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 2 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -