oj.uz

Submission #306098

# Submission time Handle Problem Language Result Execution time Memory
306098 2020-09-24T13:58:10 Z shivensinha4 Biochips (IZhO12_biochips) C++17
100 / 100
 446 ms 22136 KB 
#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] = min(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]);
	//cout << p+1 << ": " << endl;
	//for_(i, 0, dp[p].size()) if (dp[p][i] != 0) cout << i << " -> " << dp[p][i] << endl; 
}


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

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

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 8 ms 9728 KB Output is correct
3 Correct 8 ms 9728 KB Output is correct
4 Correct 13 ms 10368 KB Output is correct
5 Correct 14 ms 10368 KB Output is correct
6 Correct 15 ms 10496 KB Output is correct
7 Correct 252 ms 18556 KB Output is correct
8 Correct 238 ms 18552 KB Output is correct
9 Correct 329 ms 20856 KB Output is correct
10 Correct 446 ms 22136 KB Output is correct