Submission #1197678

#TimeUsernameProblemLanguageResultExecution timeMemory
1197678A_M_NamdarWells (CEOI21_wells)C++20
0 / 100
0 ms584 KiB
#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) { dp[u] = h[u]; if (par == -1) h[u] = 0; 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)) < k - 1) { // cout << u << ' ' << 111111111111111 << '\n'; return false; } if (min(maxi, h[u] + k - (h[u] % k) - 1) + min(maxi2, h[u] + k - (h[u] % k) - 1) >= k) { // cout << u << ' ' << 2222222222222 << '\n'; 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() { cout << "YES\n" << 1; return; for (int i = 0; i < n; i++) { // cout << i << ' ' << dfs(i, -1) << '\n'; 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(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...