이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
vector<long long> haha[400001];
vector<long long> c(400001);
vector<long long> dp(400001);
vector<long long> wow(400001);
priority_queue<pair<long long,long long>> idk[400001];
void dfs(long long a) {
for(long long v: haha[a]) {
dfs(v);
}
long long br = 0;
idk[a].push({0,a});
wow[a] = c[a];
while(!idk[a].empty()) {
pair<long long,long long> b = idk[a].top();
idk[a].pop();
if(b.first == LLONG_MAX) {
break;
}
dp[a] = max(dp[a],-br-b.first);
br+=wow[b.second];
if(idk[b.second].size() > idk[a].size()) {
swap(idk[b.second],idk[a]);
}
if(b.second != a) {
while(!idk[b.second].empty()) {
idk[a].push(idk[b.second].top());
idk[b.second].pop();
}
}
if(br > 0) {
break;
}
}
if(br <= 0) {
dp[a] = LLONG_MAX;
}
else {
wow[a] = br;
}
}
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... |