#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <unordered_set>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <random>
#include <cfloat>
#include <chrono>
#include <bitset>
#include <complex>
#include <immintrin.h>
#include <cassert>
void dfs2(int32_t v, std::vector<int32_t>* tree, int32_t* subtree_sizes) {
subtree_sizes[v] = 1;
for(int32_t i = 0; i < tree[v].size(); i++) {
dfs2(tree[v][i], tree, subtree_sizes);
subtree_sizes[v] += subtree_sizes[tree[v][i]];
}
}
int32_t m;
void dfs(int32_t v, std::vector<int32_t>* tree, int32_t** dp, int32_t* arr, int32_t* subtree_sizes) {
if(tree[v].size() == 0) {
dp[v] = new int32_t[m + 1];
dp[v][0] = 0;
dp[v][1] = arr[v];
for(int32_t i = 2; i <= m; i++)
dp[v][i] = -1'000'000'000;
return;
}
int32_t best_ind = 0;
for(int32_t i = 0; i < tree[v].size(); i++)
if(subtree_sizes[tree[v][i]] > subtree_sizes[tree[v][best_ind]])
best_ind = i;
std::swap(tree[v][best_ind], tree[v][0]);
for(int32_t i = 0; i < tree[v].size(); i++)
dfs(tree[v][i], tree, dp, arr, subtree_sizes);
dp[v] = dp[tree[v][0]];
int32_t* tmp = new int32_t[m + 1];
for(int32_t i = 1; i < tree[v].size(); i++) {
for(int32_t j = 0; j <= m; j++) {
tmp[j] = -1'000'000'000;
for(int32_t k = 0; k <= std::min(j, subtree_sizes[tree[v][i]]); k++)
tmp[j] = std::max(tmp[j], dp[v][j - k] + dp[tree[v][i]][k]);
}
int32_t* tmp2 = dp[v];
dp[v] = tmp;
tmp = tmp2;
}
dp[v][1] = std::max(dp[v][1], arr[v]);
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int32_t n;
std::cin >> n >> m;
int32_t* arr = new int32_t[n];
std::vector<int32_t>* tree = new std::vector<int32_t>[n];
int32_t root = -1;
for(int32_t i = 0; i < n; i++) {
int32_t parent;
std::cin >> parent >> arr[i];
parent--;
if(parent == -1)
root = i;
else
tree[parent].push_back(i);
}
int32_t* subtree_sizes = new int32_t[n];
dfs2(root, tree, subtree_sizes);
int32_t** dp = new int32_t*[n];
dfs(root, tree, dp, arr, subtree_sizes);
std::cout << dp[root][m];
return 0;
}
Compilation message
biochips.cpp: In function 'void dfs2(int32_t, std::vector<int>*, int32_t*)':
biochips.cpp:26:26: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | for(int32_t i = 0; i < tree[v].size(); i++) {
| ~~^~~~~~~~~~~~~~~~
biochips.cpp: In function 'void dfs(int32_t, std::vector<int>*, int32_t**, int32_t*, int32_t*)':
biochips.cpp:44:26: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(int32_t i = 0; i < tree[v].size(); i++)
| ~~^~~~~~~~~~~~~~~~
biochips.cpp:49:26: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(int32_t i = 0; i < tree[v].size(); i++)
| ~~^~~~~~~~~~~~~~~~
biochips.cpp:54:26: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int32_t i = 1; i < tree[v].size(); i++) {
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
7 ms |
3020 KB |
Output is correct |
| 5 |
Correct |
9 ms |
3916 KB |
Output is correct |
| 6 |
Correct |
12 ms |
4840 KB |
Output is correct |
| 7 |
Correct |
412 ms |
182664 KB |
Output is correct |
| 8 |
Correct |
421 ms |
184132 KB |
Output is correct |
| 9 |
Correct |
480 ms |
288716 KB |
Output is correct |
| 10 |
Correct |
672 ms |
390780 KB |
Output is correct |
