Submission #352335

#	Time	Username	Problem	Language	Result	Execution time	Memory
352335		rqi	Biochips (IZhO12_biochips)	C++14	100 / 100	600 ms	21484 KiB

biochips

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;

#define pb push_back
#define f first
#define s second
#define mp make_pair

#define sz(x) (int)(x).size()

const int mx = 200005;
int N, M;
vi children[mx];
int x[mx];
vi dp[mx];

void genDP(int node){
	dp[node] = vi{0};
	for(auto u: children[node]){
		genDP(u);

		vi res = vi(min(M+1, sz(dp[node])+sz(dp[u])-1), 0);
		for(int i = 0; i < sz(dp[node]); i++){
			for(int j = 0; j < min(M+1-i, sz(dp[u])); j++){
				res[i+j] = max(res[i+j], dp[node][i]+dp[u][j]);
			}
		}
		dp[node] = res;
	}

	if(sz(dp[node]) < 2){
		dp[node].pb(0);
	}

	dp[node][1] = max(dp[node][1], x[node]);
}

int main(){
	cin >> N >> M;

	for(int i = 1; i <= N; i++){
		int p;
		cin >> p >> x[i];
		children[p].pb(i);
	}

	genDP(0);

	cout << dp[0][M] << "\n";
}

• Subtask 1: 100 / 100