Submission #1207025

#TimeUsernameProblemLanguageResultExecution timeMemory
1207025HishamAlshehriBiochips (IZhO12_biochips)C++20
100 / 100
791 ms402456 KiB
#include <bits/stdc++.h> using namespace std; // #define int long long constexpr int maxn = 300001; int n, m, a[maxn], siz[maxn]; vector<int> dp[maxn], adj[maxn]; int sizfind(int v) { siz[v] = 1; for (int u : adj[v]) siz[v] += sizfind(u); return siz[v]; } void dfs(int v) { vector<int> ret; ret.resize(m + 5, 0); for (int u : adj[v]) { dfs(u); for (int j = 0; j <= min(siz[u], m); j++) { for (int k = 0; k + j <= min(m, siz[v]); k++) { dp[v][j + k] = max(dp[v][j + k], ret[k] + dp[u][j]); } } ret = dp[v]; } dp[v][1] = max(dp[v][1], a[v]); for (int i = 0; i <= min(siz[v], m); i++) dp[v][i] = max(dp[v][i], ret[i]); return; } signed main() { cin.tie(0) -> sync_with_stdio(0); cin >> n >> m; int rt = 0; for (int i = 1; i <= n; i++) { int p, x; cin >> p >> x; a[i] = x; if (!p) {rt = i; continue;} adj[p].push_back(i); } for (int i = 1; i <= n; i++) dp[i].resize(m + 5, 0); for (int i = 1; i <= n; i++) dp[i][0] = 0; sizfind(rt); dfs(rt); // for (int i = 1; i <= n; i++) { // for (int j = 0; j <= m; j++) cout << dp[i][j] << ' '; // cout << "\n"; // } // for (int i = 1; i <= n; i++) cout << siz[i] << " "; cout << dp[rt][m]; }
#Verdict Execution timeMemoryGrader output
Fetching results...