oj.uz

Submission #1078004

# Submission time Handle Problem Language Result Execution time Memory
1078004 2024-08-27T11:32:39 Z coolboy19521 Biochips (IZhO12_biochips) C++17
100 / 100
 405 ms 8744 KB 
// 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 + 1, (int)a.size() + (int)b.size() - 1));
    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 (1 == (int) r.size())
        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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 4 ms 4956 KB Output is correct
4 Correct 6 ms 5212 KB Output is correct
5 Correct 7 ms 5212 KB Output is correct
6 Correct 12 ms 5212 KB Output is correct
7 Correct 181 ms 8276 KB Output is correct
8 Correct 282 ms 8272 KB Output is correct
9 Correct 349 ms 8304 KB Output is correct
10 Correct 405 ms 8744 KB Output is correct