Submission #90369

#	Time	Username	Problem	Language	Result	Execution time	Memory
90369		popovicirobert	Biochips (IZhO12_biochips)	C++14	100 / 100	889 ms	398192 KiB

biochips

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const int INF = 1e9;
const int MAXN = (int) 2e5;
const int MAXM = 500;

vector <int> g[MAXN + 1];
int vals[MAXN + 1], weight[MAXN + 1];

int dp[MAXN + 1][MAXM + 1];
int m;

void dfs(int nod) {
    for(int i = 1; i <= m; i++) {
        dp[nod][i] = -INF;
    }
    for(auto it : g[nod]) {
        dfs(it);
        for(int i = min(weight[nod], m); i >= 0; i--) {
            for(int j = min(weight[it], m); j >= 0; j--) {
                if(dp[nod][i] >= 0 && dp[it][j] >= 0 && i + j <= m) {
                    dp[nod][i + j] = max(dp[nod][i + j], dp[nod][i] + dp[it][j]);
                }
            }
        }
        weight[nod] += weight[it];
    }
    weight[nod]++;
    dp[nod][1] = max(dp[nod][1], vals[nod]);
}

int main() {
    //ifstream cin("B.in");
    //ofstream cout("B.out");
    int i, n;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    int root;
    for(i = 1; i <= n; i++) {
        int par;
        cin >> par >> vals[i];
        g[par].push_back(i);
        if(par == 0) {
            root = i;
        }
    }
    dfs(root);
    cout << dp[root][m];
    //cin.close();
    //cout.close();
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 100 / 100