Submission #1275579

#TimeUsernameProblemLanguageResultExecution timeMemory
1275579rtriCat in a tree (BOI17_catinatree)C++20
11 / 100
2 ms648 KiB
#include <bits/stdc++.h> using namespace std; int n, d; vector<vector<int>> adj; pair<int, int> dfs(int u, int p = -1) { vector<pair<int, int>> c; for (int v : adj[u]) if (v != p) { auto [ans, length] = dfs(v, u); c.push_back({length, ans}); } sort(c.begin(), c.end()); vector<int> pref(c.size() + 1); for (int i = 0; i < c.size(); i++) pref[i + 1] = pref[i] + c[i].second; int ans = 0, length = d; for (int i = 0; i < c.size(); i++) { int a = c[i].second; for (int j = i + 1; j < c.size(); j++) { if (d <= c[j].first + c[i].first) a += c[j].second; else break; } // cerr << "RES " << i << " " << a << endl; if (ans < a || (ans == a && c[i].first > length)) { length = c[i].first; ans = a; } } if (d <= length) { ans++; length = 0; } // cerr << "NODE " << u << " " << ans << " " << length << endl; return {ans, length + 1}; } int main() { cin >> n >> d; adj.resize(n); for (int u = 1; u < n; u++) { int v; cin >> v; adj[u].push_back(v); adj[v].push_back(u); } auto [ans, length] = dfs(0); cout << ans << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...