Submission #1276968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276968		SnowRaven52	Biochips (IZhO12_biochips)	C++20	100 / 100	269 ms	7836 KiB

biochips

#include <bits/stdc++.h>
using namespace std;

static const int NEG = -1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; cin >> n >> m;

    vector<int> par(n + 1, 0), w(n + 1, 0);
    vector<vector<int>> ch(n + 1);
    int root = -1;
    for (int i = 1; i <= n; i++) {
        int p, x; cin >> p >> x;
        par[i] = p; w[i] = x;
        if (p == 0) root = i;
        else ch[p].push_back(i);
    }

    struct Frame {
        int v;
        int idx;
        vector<int> acc;
    };

    auto merge_into = [&](vector<int> &acc, const vector<int> &child) {
        int a = (int)acc.size() - 1;
        int b = (int)child.size() - 1;
        int lim = min(m, a + b);
        vector<int> ndp(lim + 1, NEG);
        for (int i = 0; i <= a; i++) if (acc[i] > NEG) {
            for (int j = 0; j <= b && i + j <= lim; j++) if (child[j] > NEG) {
                ndp[i + j] = max(ndp[i + j], acc[i] + child[j]);
            }
        }
        acc.swap(ndp);
    };

    vector<Frame> st;
    st.push_back({root, 0, vector<int>(1, 0)});
    vector<int> result_root;

    while (!st.empty()) {
        Frame &f = st.back();
        if (f.idx < (int)ch[f.v].size()) {
            int u = ch[f.v][f.idx++];
            st.push_back({u, 0, vector<int>(1, 0)});
        } else {
            if ((int)f.acc.size() < 2) f.acc.resize(2, NEG);
            f.acc[1] = max(f.acc[1], w[f.v]);
            if ((int)f.acc.size() > m + 1) f.acc.resize(m + 1);

            vector<int> cur = move(f.acc);
            st.pop_back();
            if (st.empty()) {
                result_root = move(cur);
            } else {
                merge_into(st.back().acc, cur);
            }
        }
    }

    cout << result_root[m] << endl;
}

• Subtask 1: 100 / 100