oj.uz

Submission #893658

# Submission time Handle Problem Language Result Execution time Memory
893658 2023-12-27T08:48:07 Z heeheeheehaaw Biochips (IZhO12_biochips) C++17
20 / 100
 2000 ms 407892 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")

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

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
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Incorrect 1 ms 6492 KB Output isn't correct
4 Incorrect 19 ms 25420 KB Output isn't correct
5 Incorrect 30 ms 27484 KB Output isn't correct
6 Incorrect 49 ms 27480 KB Output isn't correct
7 Execution timed out 2063 ms 303680 KB Time limit exceeded
8 Execution timed out 2056 ms 303696 KB Time limit exceeded
9 Execution timed out 2029 ms 368364 KB Time limit exceeded
10 Execution timed out 2047 ms 407892 KB Time limit exceeded