Submission #1215148

#TimeUsernameProblemLanguageResultExecution timeMemory
1215148madamadam3Cat in a tree (BOI17_catinatree)C++20
51 / 100
1098 ms14592 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, D; if (!(cin >> N >> D)) return 0; vector<vector<int>> adj(N); for (int i = 1; i < N; ++i) { int x; // parent of i cin >> x; adj[i].push_back(x); adj[x].push_back(i); } if (D == 1) { cout << N << '\n'; return 0; } vector<int> depth(N, 0), parent(N, -1); { vector<int> st = {0}; parent[0] = -2; while (!st.empty()) { int u = st.back(); st.pop_back(); for (int v : adj[u]) if (v != parent[u]) { parent[v] = u; depth[v] = depth[u] + 1; st.push_back(v); } } } int maxDepth = *max_element(depth.begin(), depth.end()); vector<vector<int>> byDepth(maxDepth + 1); for (int v = 0; v < N; ++v) byDepth[ depth[v] ].push_back(v); vector<char> blocked(N, 0); vector<int> seen(N, 0); int stamp = 1; int answer = 0; queue<pair<int,int>> q; for (int d = maxDepth; d >= 0; --d) { for (int v : byDepth[d]) { if (blocked[v]) continue; ++answer; blocked[v] = 1; q.push({v, 0}); seen[v] = stamp; while (!q.empty()) { auto [u, dist] = q.front(); q.pop(); if (dist + 1 >= D) continue; for (int w : adj[u]) { if (seen[w] == stamp) continue; seen[w] = stamp; blocked[w] = 1; q.push({w, dist + 1}); } } ++stamp; } } cout << answer << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...