이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 300'000 + 10;
int n, fund, total;
int profit[N];
vector<pair<int, int>> ad[N];
int par[N];
namespace sub1 {
int f[N];
void dfs(int u) {
auto& ret = f[u];
for (const auto& [v, w] : ad[u]) {
dfs(v);
if (f[v] + w > 0) ret += f[v] + w;
}
}
void solve() {
dfs(0);
cout << f[0] << "\n";
}
}
namespace sub3 {
int d[N], mi[N];
vector<int> nxt[N];
void dfs(int u, int pre) {
if (d[u] > 0) {
if (u) nxt[pre].push_back(u);
pre = u;
}
for (const auto& [v, w] : ad[u]) {
if (pre == u) {
d[v] = 0 + w;
mi[v] = min(0ll, w);
} else {
d[v] = d[u] + w;
mi[v] = mi[u] + min(0ll, w);
}
dfs(v, pre);
}
}
void solve() {
dfs(0, 0);
using pii = pair<int, int>;
priority_queue<pii> q;
for (const auto& x : nxt[0]) q.push({mi[x], x});
while (q.size()) {
auto [minimum, u] = q.top(); q.pop();
if (total < -minimum) break;
total += d[u];
for (const auto& v : nxt[u]) q.push({mi[v], v});
}
cout << total - fund << "\n";
}
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> fund;
for (int i = 1; i <= n; ++i) {
int w, p; cin >> w >> p;
par[i] = p;
ad[p].push_back({i, profit[i] = w});
}
total = fund;
if (fund == 1e18) { sub1::solve(); return 0; }
bool sub3 = true;
for (int i = 1; i <= n; ++i) sub3 &= (!par[i] || par[i] == i - 1);
if (sub3) { sub3::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... |