oj.uz

Submission #893657

# Submission time Handle Problem Language Result Execution time Memory
893657 2023-12-27T08:46:52 Z heeheeheehaaw Biochips (IZhO12_biochips) C++17
60 / 100
 145 ms 524288 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int INF = 2e9;
int dp[200005][505];
int newdp[505];
vector<int> adj[200005];
int val[200005];
int n, k;

void dfs(int nod, int parent)
{
    for(auto it : adj[nod])
    {
        if(it != parent)
        {
            dfs(it, nod);
            for(int i = 0; i <= k; i++)
                newdp[i] = dp[nod][i];

            for(int i = 0; i <= k; i++)
            {
                if(dp[it][i] == 0)
                    continue;

                for(int j = k - i; j >= 0; j--)
                    if(dp[nod][j] != -INF)
                        newdp[i + j] = max(newdp[i + j], dp[nod][j] + dp[it][i]);
            }

            for(int i = 0; i <= k; i++)
                dp[nod][i] = newdp[i];
        }
    }

    dp[nod][1] = max(dp[nod][1], val[nod]);
}

signed main()
{
    cin>>n>>k;
    int root;
    for(int i = 1; i <= n; i++)
    {
        int a, b;
        cin>>a>>b;
        if(a != 0)
        {
            adj[i].push_back(a);
            adj[a].push_back(i);
        }
        else
            root = i;

        val[i] = b;
    }

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= k; j++)
            dp[i][j] = -INF;

    dfs(root, root);
    cout<<dp[root][k];

    return 0;

}

Compilation message

biochips.cpp: In function 'int main()':
biochips.cpp:65:21: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |     cout<<dp[root][k];
      |                     ^

Subtask #1
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 25 ms 43936 KB Output is correct
5 Correct 36 ms 47964 KB Output is correct
6 Correct 55 ms 47964 KB Output is correct
7 Runtime error 145 ms 524288 KB Execution killed with signal 9
8 Runtime error 122 ms 524288 KB Execution killed with signal 9
9 Runtime error 130 ms 524288 KB Execution killed with signal 9
10 Runtime error 142 ms 524288 KB Execution killed with signal 9