Submission #281727

#	Time	Username	Problem	Language	Result	Execution time	Memory
281727		jun6873	Biochips (IZhO12_biochips)	C++11	100 / 100	66 ms	8908 KiB

biochips

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

const int maxn = 200004;

int N, K, a[maxn], o;
vector<int> g[maxn];

vector<int> dp(int x) {
	vector<int> res;
	for (int y : g[x]) {
		vector<int> now = dp(y);
		for (int i=now.size()-1; i>=1; i--) now[i] -= now[i-1];
		res.insert(res.end(), now.begin(), now.end());
	}
	sort(res.begin(), res.end());
	reverse(res.begin(), res.end());
	if (res.size() >= K) res.resize(K);
	for (int i=1; i<res.size(); i++) res[i] += res[i-1];

	if (res.empty()) res.push_back(a[x]);
	else res[0] = max(res[0], a[x]);

	return res;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	cin >> N >> K;
	for (int i=1; i<=N; i++) {
		int p, x;
		cin >> p >> x;

		if (p == 0) o = i;
		else g[p].push_back(i);

		a[i] = x;
	}

	cout << dp(o)[K-1] << '\n';
}

Compilation message (stderr)

biochips.cpp: In function 'std::vector<int> dp(int)':
biochips.cpp:18:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |  if (res.size() >= K) res.resize(K);
      |      ~~~~~~~~~~~^~~~
biochips.cpp:19:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for (int i=1; i<res.size(); i++) res[i] += res[i-1];
      |                ~^~~~~~~~~~~

• Subtask 1: 100 / 100