Submission #1249345

#TimeUsernameProblemLanguageResultExecution timeMemory
1249345chikien2009Cat in a tree (BOI17_catinatree)C++20
100 / 100
33 ms12104 KiB
#include <bits/stdc++.h> using namespace std; void setup() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } int n, d, a, f[200000]; vector<int> g[200000]; inline int DFS(int node, int par) { int cur = 1e9, temp; f[node] = 0; for (auto &i : g[node]) { temp = DFS(i, node); temp++; if (d <= temp + cur) { f[node] += f[i]; cur = min(cur, temp); } else { f[node] += f[i] - 1; cur = max(cur, temp); } } f[node] += (d <= cur); cur = (d <= cur ? 0 : cur); return cur; } int main() { setup(); cin >> n >> d; for (int i = 1; i < n; ++i) { cin >> a; g[a].push_back(i); } DFS(0, 0); cout << f[0]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...