Submission #1109579

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109579		12345678	Biochips (IZhO12_biochips)	C++17	100 / 100	191 ms	19552 KiB

biochips

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

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 / 100