Submission #1224047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224047		VMaksimoski008	바이오칩 (IZhO12_biochips)	C++17	90 / 100	546 ms	410176 KiB

biochips

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;

int n, m, root, p[N], a[N], dp[N][505], sub[N];
vector<int> g[N];

void dfs(int u, int p) {
    for (int v : g[u]) {
        if (v == p) continue;
        dfs(v, u);

        int temp[505];
        memcpy(temp, dp[u], sizeof(dp[u]));

        for (int i = min(m, sub[u]); i >= 0; i--) {
            for (int j = min(m - i, sub[v]); j >= 0; j--) {
                dp[u][i + j] = max(dp[u][i + j], temp[i] + dp[v][j]);
            }
        }

        sub[u] += sub[v];
    }
    sub[u]++;
    dp[u][1] = max(dp[u][1], a[u]); // Take current node as a single selection
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> p[i] >> a[i];
        if (!p[i]) {
            root = i;
        } else {
            g[p[i]].push_back(i);
            g[i].push_back(p[i]);
        }
    }

    dfs(root, root);
    cout << dp[root][m] << '\n';

    return 0;
}

• Subtask 1: 90 / 100