Submission #1197690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197690		A_M_Namdar	Wells (CEOI21_wells)	C++20	0 / 100	1 ms	584 KiB

wells

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

const int N = 1e4 + 10;
int n, k, h[N], dp[N];
vector<int> adj[N];

bool dfs(int u, int par) {
	if (par == -1) h[u] = 0;
	dp[u] = h[u];
	vector<int> vec;
	for (int v: adj[u]) 
		if (v != par) {
			h[v] = h[u] + 1;
			if (!dfs(v, u)) return false;
			dp[u] = max(dp[u], dp[v]);
			vec.push_back(dp[v]);
		}
	if (vec.size() < 2) return true;
	int maxi = 0, maxi2 = 0;
	for (int x: vec) 
		if (x > maxi2) {
			maxi2 = x;
			if (maxi2 > maxi) 
				swap(maxi, maxi2);
		}
	if (h[u] % k) {
		if (maxi2 >= h[u] + k - (h[u] % k) && 2 * (h[u] + k - (h[u] % k) - h[u]) != k) {
			return false;
		}
		if (min(maxi, h[u] + k - (h[u] % k) - 1) - h[u] + min(maxi2, h[u] + k - (h[u] % k) - 1) - h[u] >= k) {
			return false;
		}
	}
	return true;
}

void input() {
	cin >> n >> k;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
}

void solve() {
	for (int i = 0; i < n; i++) {
		if (dfs(i, -1)) {
			cout << "YES\n" << 1;
			return;
		}
	}
	cout << "NO\n" << 0;
}

int main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	input();
	solve();
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 30