제출 #955871

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
955871		Trisanu_Das	Burza (COCI16_burza)	C++17	48 / 160	1 ms	760 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";
}

컴파일 시 표준 에러 (stderr) 메시지

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
• 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