oj.uz

Submission #574455

# Submission time Handle Problem Language Result Execution time Memory
574455 2022-06-08T15:13:18 Z saarang123 Biochips (IZhO12_biochips) C++17
100 / 100
 637 ms 399456 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MXN = 200 * 1000 + 3;
const int MXM = 503;
int dp[MXN][MXM], a[MXN], sz[MXN];
vector<int> g[MXN];
int n, m;

void dfs(int v) {
	sz[v] = max(1, (int) g[v].size());
	for(int u : g[v]) {
		dfs(u);
		for(int i = min(m, sz[v]); i >= 0; i--)
			for(int j = 0; j <= min(sz[u], m - i); j++) if(dp[v][i] != -1 && dp[u][j] != -1)
				dp[v][i + j] = max(dp[v][i + j], dp[v][i] + dp[u][j]);
		sz[v] += sz[u];
	}
	dp[v][1] = max(dp[v][1], a[v]);
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    cin >> n >> m;
    int r = -1;
    for(int p, i = 1; i <= n; i++) {
    	cin >> p >> a[i];
    	dp[i][0] = 0;
    	for(int j = 1; j <= m; j++)
    		dp[i][j] = -1;
    	if(p) {
    		g[p].push_back(i);
    	}
    	else
    		r = i;
    }
    dfs(r);
    // for(int i = 1; i <= n; i++) {
    // 	for(int j = 1; j <= m; j++) 
    // 		cout << dp[i][j] << ' ';
    // 	cout << '\n';
    // }
    cout << dp[r][m] << '\n';
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5212 KB Output is correct
4 Correct 13 ms 22612 KB Output is correct
5 Correct 19 ms 24912 KB Output is correct
6 Correct 17 ms 24920 KB Output is correct
7 Correct 325 ms 297616 KB Output is correct
8 Correct 332 ms 297640 KB Output is correct
9 Correct 509 ms 361904 KB Output is correct
10 Correct 637 ms 399456 KB Output is correct