Submission #306101

#	Time	Username	Problem	Language	Result	Execution time	Memory
306101		shivensinha4	Biochips (IZhO12_biochips)	C++17	0 / 100	2065 ms	80720 KiB

biochips

#include <bits/stdc++.h> 
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'

int n, m;
const int MXN = 2e5, MXM = 500;
vi adj[MXN+1], dp[MXN+1];
int val[MXN+1], lf[MXN+1];

void dfs(int p, int parent) {
	lf[p] = !adj[p].size();
	for (int i: adj[p]) if (i != parent) {
		dfs(i, p);
		lf[p] += lf[i];
	}
	lf[p] = m;
	dp[p].resize(lf[p]+1);
	for (int i: adj[p]) {
		vi curr = dp[p];
		for_(j, 0, lf[p]+1) if (j == 0 or dp[p][j] != 0) for_(k, 1, min(lf[i]+1, lf[p]-j+1)) if (dp[i][k] != 0) {
			curr[j+k] = max(curr[j+k], dp[p][j] + dp[i][k]);
		}
		swap(curr, dp[p]);
	}
	
	dp[p][1] = max(dp[p][1], val[p]);
}


int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int rt; cin >> n >> m;
	for_(i, 0, n) {
		int p; cin >> p >> val[i];
		if (p != 0) adj[p-1].push_back(i);
		else rt = i;
	}
	
	dfs(rt, rt);
	cout << dp[rt][m] << endl;

	return 0;
}

Compilation message (stderr)

biochips.cpp: In function 'int main()':
biochips.cpp:43:6: warning: 'rt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   43 |  int rt; cin >> n >> m;
      |      ^~

• Subtask 1: 0 / 100