oj.uz

Submission #90369

# Submission time Handle Problem Language Result Execution time Memory
90369 2018-12-21T11:29:53 Z popovicirobert Biochips (IZhO12_biochips) C++14
100 / 100
 889 ms 398192 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 5 ms 5112 KB Output is correct
3 Correct 5 ms 5312 KB Output is correct
4 Correct 24 ms 22864 KB Output is correct
5 Correct 26 ms 24996 KB Output is correct
6 Correct 27 ms 25040 KB Output is correct
7 Correct 489 ms 296844 KB Output is correct
8 Correct 489 ms 296844 KB Output is correct
9 Correct 634 ms 360788 KB Output is correct
10 Correct 889 ms 398192 KB Output is correct