Submission #1190505

#TimeUsernameProblemLanguageResultExecution timeMemory
1190505KaleemRazaSyedWells (CEOI21_wells)C++20
0 / 100
18 ms35656 KiB
#include<bits/stdc++.h> using namespace std; const int N = 1.5e6 + 10, mod = 1e9+7; int n, k; vector<int> G[N]; bool done[N]; int dfs(int v, int p = -1) { int ans = 0; for(int u : G[v]) if(u != p) ans = max(ans, 1 + dfs(u, v)); return ans; } int diameter() { int ans = 0; for(int v = 1; v <= n; v ++) ans = max(ans, dfs(v)); return ans; } bool check(int v) { bool seen[n + 1] = {}; seen[v] = 1; vector<int> level = {v}; int l = 0; vector<int> vec; while(level.size()) { if(l % k == 0) for(int v : level) vec.push_back(v); vector<int> nl; for(int v : level) { int cnt = 0; for(int u : G[v]) if(!seen[u]) cnt++, seen[u] = 1, nl.push_back(u); if(cnt > 1 && l % k == k-1) return false; } l++; level = nl; } for(int v : vec) done[v] = 1; return true; } int main() { cin >> n >> k; if(k == 2) { cout << "YES\n"; cout << 2 << endl; return 0; } for(int i = 1; i < n; i ++) { int a, b; cin >> a >> b; G[a].push_back(b); G[b].push_back(a); } int x = diameter(); if(x < k) { cout << "YES\n"; int ans = 1; for(int i = 0; i < n; i ++) ans = (ans * 2) % mod; cout << ans << endl; return 0; } int ans = 0; for(int v = 1; v <= n; v++) if(!done[v]) ans += check(v); cout << (ans == 0 ? "NO" : "YES") << endl; cout << ans << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...