oj.uz

Submission #955871

# Submission time Handle Problem Language Result Execution time Memory
955871 2024-03-31T15:53:40 Z Trisanu_Das Burza (COCI16_burza) C++17
48 / 160
 1 ms 760 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";
}

Compilation message

burza.cpp: In function 'int main()':
burza.cpp:68:6: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   68 |   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));
      |      ^

Subtask #1
0 / 16.0

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

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 1 ms 348 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 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #4
16.0 / 16.0

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

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Incorrect 1 ms 348 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 348 KB Output is correct
2 Correct 1 ms 484 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 1 ms 484 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 488 KB Output is correct
5 Incorrect 1 ms 348 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 760 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 484 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #9
0 / 16.0

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

Subtask #10
0 / 16.0

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