oj.uz

Submission #1109579

# Submission time Handle Problem Language Result Execution time Memory
1109579 2024-11-07T05:54:41 Z 12345678 Biochips (IZhO12_biochips) C++17
100 / 100
 191 ms 19552 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5, kx=505;

int n, m, p, sz[nx], rt;
vector<int> d[nx];
vector<int> dp[nx];

void dfs(int u)
{
    for (auto v:d[u])
    {
        dfs(v);
        if (dp[v].size()>dp[u].size()) swap(dp[u], dp[v]);
        //if (u==3) cout<<"debug "<<u<<' '<<dp[u].size()<<' '<<v<<' '<<dp[v].size()<<'\n';
        if (dp[v].empty()) continue;
        int tmp=min(m+1, (int)dp[u].size()+(int)dp[v].size()-1);
        while (dp[u].size()<tmp) dp[u].push_back(0);
        //if (u==3) cout<<"debug "<<u<<' '<<dp[u].size()<<' '<<v<<' '<<dp[v].size()<<'\n';
        //if (u==3) for (int i=0; i<dp[u].size(); i++) cout<<dp[u][i]<<' ';
        //if (u==3) cout<<'\n';
        vector<int> nxt(tmp);
        for (int i=1; i<dp[v].size(); i++)
        {
            for (int j=i; j<tmp; j++) nxt[j]=max(nxt[j], dp[u][j-i]+dp[v][i]);
        }
        for (int i=1; i<tmp; i++) dp[u][i]=max(dp[u][i], nxt[i]);
        dp[v].clear();
    }
    if (dp[u].size()<2) dp[u].push_back(0), dp[u].push_back(0);
    dp[u][1]=max(dp[u][1], sz[u]);
    //cout<<"finish "<<u<<":";
    //for (int i=0; i<dp[u].size(); i++) cout<<dp[u][i]<<' ';
    //cout<<'\n';
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=n; i++) 
    {
        cin>>p>>sz[i];
        if (p) d[p].push_back(i);
        else rt=i;
    }
    dfs(rt);
    cout<<dp[rt][m];
}

Compilation message

biochips.cpp: In function 'void dfs(int)':
biochips.cpp:20:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   20 |         while (dp[u].size()<tmp) dp[u].push_back(0);
      |                ~~~~~~~~~~~~^~~~
biochips.cpp:25:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for (int i=1; i<dp[v].size(); i++)
      |                       ~^~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9808 KB Output is correct
2 Correct 3 ms 9808 KB Output is correct
3 Correct 3 ms 9808 KB Output is correct
4 Correct 5 ms 10064 KB Output is correct
5 Correct 6 ms 10336 KB Output is correct
6 Correct 7 ms 10320 KB Output is correct
7 Correct 91 ms 18504 KB Output is correct
8 Correct 85 ms 18504 KB Output is correct
9 Correct 132 ms 18504 KB Output is correct
10 Correct 191 ms 19552 KB Output is correct