#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 200050
using ll = long long;
int n, m, p[N], a[N], in[N], out[N], timer, dp[502][N];
vector<int> g[N];
vector<tuple<int, int, int>> v;
void dfs(int u)
{
in[u] = timer++;
for (auto v : g[u]) dfs(v);
out[u] = timer++;
v.emplace_back(out[u], in[u], a[u]);
}
void schedule()
{
for (int j = 1; j <= m; ++j)
{
for (auto i = 0; i < v.size(); ++i)
{
auto [e, s, w] = v[i];
int l = 0, r = i-1;
dp[j][i] = i?dp[j][i-1]:w;
while (l <= r)
{
int y = (l+r)/2;
if (get<0>(v[y]) < s)
dp[j][i] = max(dp[j][i], dp[j-1][y] + w), l = y + 1;
else r = y - 1;
}
}
}
}
int main()
{
ShinLena;
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> p[i] >> a[i], g[p[i]].push_back(i);
dfs(0);
sort(ALL(v));
schedule();
cout << dp[m][v.size()-1];
return 0;
}
Compilation message
biochips.cpp: In function 'void schedule()':
biochips.cpp:31:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for (auto i = 0; i < v.size(); ++i)
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8796 KB |
Output is correct |
| 3 |
Correct |
4 ms |
23180 KB |
Output is correct |
| 4 |
Correct |
22 ms |
56348 KB |
Output is correct |
| 5 |
Correct |
28 ms |
66764 KB |
Output is correct |
| 6 |
Correct |
35 ms |
85008 KB |
Output is correct |
| 7 |
Correct |
1914 ms |
249192 KB |
Output is correct |
| 8 |
Correct |
1826 ms |
248748 KB |
Output is correct |
| 9 |
Execution timed out |
2013 ms |
256840 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2065 ms |
248888 KB |
Time limit exceeded |
