Submission #1077997

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077997		coolboy19521	Biochips (IZhO12_biochips)	C++17	60 / 100	342 ms	15368 KiB

biochips

// It looks like nk^2 but is not. Code is very similar to Benq's because I was analyzing his code to understand why the idea I have thought is not nk^2. The reason is that it is not very probable to have two children.

#include "bits/stdc++.h"
#define ll long long

using namespace std;

const int sz = 2e5 + 10;

vector<int> aj[sz];
int vl[sz];
int m;

vector<int> comb(vector<int> a, vector<int> b) {
    vector<int> c(min(m, (int)a.size() + (int)b.size()));
    for (int i = 0; i < (int) a.size(); i ++)
        for (int j = 0; j < (int) b.size() && i + j <= m; j ++)
            c[i + j] = max(c[i + j], a[i] + b[j]);
    return c;
}

vector<int> dfs(int v) {
    vector<int> r = {0};
    for (int u : aj[v])
        r = comb(r, dfs(u));
    if (aj[v].empty())
        r.push_back(0);
    r[1] = max(r[1], vl[v]);
    return r;
}

int main() {
    int n;
    cin >> n >> m;

    for (int i = 1; i <= n; i ++) {
        int p;
        cin >> p >> vl[i];
        aj[p].push_back(i);
    }

    auto r = dfs(aj[0][0]);
    cout << r[m] << '\n';
}

• Subtask 1: 60 / 100