oj.uz

Submission #1077997

# Submission time Handle Problem Language Result Execution time Memory
1077997 2024-08-27T11:30:19 Z coolboy19521 Biochips (IZhO12_biochips) C++17
60 / 100
 342 ms 15368 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, (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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Runtime error 5 ms 10076 KB Execution killed with signal 11
4 Incorrect 6 ms 5212 KB Output isn't correct
5 Correct 10 ms 5212 KB Output is correct
6 Correct 8 ms 5212 KB Output is correct
7 Correct 169 ms 8140 KB Output is correct
8 Correct 171 ms 8276 KB Output is correct
9 Runtime error 53 ms 15368 KB Execution killed with signal 6
10 Incorrect 342 ms 8616 KB Output isn't correct