이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
const ll INF = 2e18;
void DFS(int v, vector<vector<int>>& adj, vector<ll>& dp, vector<int>& x, vector<set<pair<ll, ll>>>& stack){
for(int node : adj[v]){
DFS(node, adj, dp, x, stack);
if((int)stack[node].size() > (int)stack[v].size()) swap(stack[node], stack[v]);
for(pair<ll, ll> pr : stack[node]){ //Not so complex now, as I am maintaining sum only.
stack[v].insert(pr);
}
}
ll minPre = max(0ll, -x[v]); //The max 0 is just if it's positive. For convenience, i don't want it to be neg.
ll sum = x[v];
while(sum <= 0 && !stack[v].empty()){
pair<ll, ll> pr = *stack[v].begin(); stack[v].erase(stack[v].begin());
minPre = max(minPre, pr.first - sum); sum += pr.second;
}
if(sum <= 0) return;
//Now, because I am the root, my children can't be taken without me, so I need to erase the ones
//with minPre lower than mine.
while(!stack[v].empty() && (*stack[v].begin()).first < minPre){
pair<ll, ll> pr = *stack[v].begin(); stack[v].erase(stack[v].begin());
sum += pr.second;
}
stack[v].insert({minPre, sum});
dp[v] = minPre;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int N; ll s; cin >> N >> s;
ll orgs = s;
vector<int> x(N), p(N);
vector<vector<int>> adj(N);
for(int i = 0; i < N; i++){
cin >> x[i] >> p[i]; p[i]--;
if(p[i] != -1){
adj[p[i]].push_back(i);
}
}
vector<ll> dp(N, INF); //Min cost until profit.
vector<set<pair<ll, ll>>> stack(N);
for(int i = 0; i < N; i++){
if(p[i] == -1) DFS(i, adj, dp, x, stack);
}
priority_queue<pair<ll, int>> q;
for(int i = 0; i < N; i++){
if(p[i] == -1){
q.push({-dp[i], i});
}
}
while(!q.empty() && -q.top().first <= s){
int v = q.top().second; q.pop();
s += x[v];
for(int node : adj[v]){
q.push({-dp[node], node});
}
}
cout << s - orgs << "\n";
}
# | 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... |