이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
typedef long long llong;
const int MAXN = 300000 + 10;
const int MOD = 1e9 + 7;
const llong INF = 1e18;
const int INTINF = 1e9;
int n;
struct Eat
{
llong required;
llong profit;
friend Eat operator + (const Eat &a, const Eat &b)
{
if (a.required > b.required)
{
return b + a;
}
return {std::max(0LL, std::max(a.required, b.required - a.profit)), a.profit + b.profit};
}
};
llong a[MAXN];
llong dp[MAXN];
std::vector <int> g[MAXN];
std::vector <Eat> eat[MAXN];
void dfs(int node, int par)
{
eat[node].push_back({0, 0});
for (const int &u : g[node])
{
if (u != par)
{
dfs(u, node);
std::vector <Eat> result;
for (const Eat &first : eat[node])
{
for (const Eat &second : eat[u])
{
result.push_back(first + second);
}
}
eat[node] = result;
}
}
for (Eat &curr : eat[node])
{
curr.required = std::max(0LL, std::max(-a[node], curr.required - a[node]));
curr.profit += a[node];
}
if (a[node] < 0)
{
eat[node].push_back({0, 0});
}
// std::cout << "eat: " << node << '\n';
// for (const auto &[required, profit] : eat[node])
// {
// std::cout << required << ' ' << profit << '\n';
// }
}
void solve()
{
dfs(1, 0);
llong max = 0;
for (const Eat ¤t : eat[1])
{
if (current.required == 0)
{
max = std::max(max, current.profit);
}
}
assert(max >= a[1]);
std::cout << max - a[1] << '\n';
}
void input()
{
std::cin >> n >> a[1]; n++;
for (int i = 2 ; i <= n ; ++i)
{
int p;
std::cin >> a[i] >> p;
g[p + 1].push_back(i);
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |