Submission #893661

#	Time	Username	Problem	Language	Result	Execution time	Memory
893661		heeheeheehaaw	Biochips (IZhO12_biochips)	C++17	60 / 100	2067 ms	407932 KiB

biochips

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")

using namespace std;

const int INF = 2e8;
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()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    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 (stderr)

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

• Subtask 1: 60 / 100