oj.uz

Submission #343002

# Submission time Handle Problem Language Result Execution time Memory
343002 2021-01-03T10:46:37 Z apostoldaniel854 Biochips (IZhO12_biochips) C++14
100 / 100
 473 ms 401004 KB 
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"
using ll = long long;

const int MAX_N = 2e5, MAX_M = 500;

int dp[1 + MAX_N + 1][1 + MAX_M];
int sz[1 + MAX_N];
int tag[1 + MAX_N], order[1 + MAX_N];
int memo[1 + MAX_N];

vector <int> gr[1 + MAX_N];

int nr = 0;
void dfs_prec (int node) {
    sz[node] = 1;
    order[++nr] = node;
    tag[nr] = node;
    for (int son : gr[node]) {
        dfs_prec (son);
        sz[node] += sz[son];
    }
}
void upd (int &a, int b) {
    if (a < b)
        a = b;
}

int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    int n, m;
    cin >> n >> m;
    int root;
    for (int i = 1; i <= n; i++) {
        int par;
        cin >> par >> memo[i];
        if (par)
            gr[par].pb (i);
        else
            root = i;
    }
    dfs_prec (root);
    for (int i = 0; i <= n + 1; i++)
        for (int j = 0; j <= m; j++)
            dp[i][j] = -(1 << 30);
    dp[n + 1][0] = 0;
    for (int i = n; i > 0; i--) {
        int node = tag[i];
        int from = i + sz[node];
        for (int j = 1; j <= m; j++)
            upd (dp[i][j], dp[from][j - 1] + memo[node]);
        for (int j = 0; j <= m; j++) {
            upd (dp[i][j], dp[i + 1][j]);
 ///           dbg (i); dbg (j);
 ///           dbg (dp[i][j]);
        }
    }
    cout << dp[1][m] << "\n";
    return 0;
}

Compilation message

biochips.cpp: In function 'int main()':
biochips.cpp:47:14: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |     dfs_prec (root);
      |     ~~~~~~~~~^~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Correct 3 ms 5100 KB Output is correct
3 Correct 4 ms 5228 KB Output is correct
4 Correct 16 ms 22764 KB Output is correct
5 Correct 18 ms 24940 KB Output is correct
6 Correct 19 ms 24940 KB Output is correct
7 Correct 293 ms 297836 KB Output is correct
8 Correct 298 ms 299244 KB Output is correct
9 Correct 390 ms 363244 KB Output is correct
10 Correct 473 ms 401004 KB Output is correct