oj.uz

Submission #281727

# Submission time Handle Problem Language Result Execution time Memory
281727 2020-08-23T11:08:27 Z jun6873 Biochips (IZhO12_biochips) C++11
100 / 100
 66 ms 8908 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 7 ms 5248 KB Output is correct
5 Correct 9 ms 5248 KB Output is correct
6 Correct 8 ms 5248 KB Output is correct
7 Correct 63 ms 8908 KB Output is correct
8 Correct 61 ms 8908 KB Output is correct
9 Correct 60 ms 8184 KB Output is correct
10 Correct 66 ms 8568 KB Output is correct