This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
vector<long long> haha[400001];
vector<long long> c(400001);
vector<long long> dp(400001);
void dfs(long long a) {
for(long long v: haha[a]) {
dfs(v);
}
long long br = 0;
priority_queue<pair<long long,long long>> idk;
idk.push({-c[a],a});
while(!idk.empty()) {
pair<long long,long long> b = idk.top();
idk.pop();
br+=c[b.second];
if(br > 0) {
break;
}
dp[a] = max(dp[a],-br);
for(long long v: haha[b.second]) {
idk.push({-dp[v],v});
}
}
if(br <= 0) {
dp[a] = LLONG_MAX;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long n,s,p;
cin >> n >> s;
for(long long i = 1; i <= n; i++) {
cin >> c[i] >> p;
haha[p].push_back(i);
}
dfs(0);
long long ans = s,br = s;
priority_queue<pair<long long,long long>> idk;
idk.push({-dp[0],0});
while(!idk.empty()) {
pair<long long,long long> b = idk.top();
idk.pop();
if(b.first > br) {
break;
}
br+=c[b.second];
ans = max(ans,br);
for(long long v: haha[b.second]) {
idk.push({-dp[v],v});
}
}
cout << ans-s;
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... |