Submission #1190549

#TimeUsernameProblemLanguageResultExecution timeMemory
1190549KaleemRazaSyedWells (CEOI21_wells)C++20
0 / 100
46 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 mark[N]; bool Close; void Dfs(int v, int p = -1, int d = 1) { if(Close || d > k) return; if(d <= k && d != 1) Close |= mark[v]; for(int u : G[v]) if(u != p) Dfs(u, v, d + 1); } void dFs(int v, int p = -1, int d = 1) { if(Close || d > k) return; if(d == k) Close = true; for(int u : G[v]) { if(u == p) continue; if(!mark[u]) dFs(u, v, d + 1); } } bool check(int v) { bool seen[n + 1] = {}; memset(seen, false, sizeof(seen)); seen[v] = 1; vector<int> level = {v}; int l = 1; vector<int> vec; Close = false; while(level.size()) { // cerr << l << endl; if(l == 1) for(int x : level) vec.push_back(x); vector<int> nl; for(int x : level) for(int u : G[x]) if(!seen[u]) seen[u] = 1, nl.push_back(u); l = l % k + 1; level = nl; } // cerr << "k = " << k << endl; // cerr << "vec = "; for(int u : vec) { // cerr << u << ' '; mark[u] = true; } // cerr << endl; for(int i = 1; i <= n; i ++) if(mark[i]) Dfs(i); else dFs(i); for(int v : vec) mark[v] = false; return !Close; } 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 ans = 0; for(int v = 1; v <= n; 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...