#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
void DFS(int v, vector<vector<int>>& adj, vector<ll>& dp, vector<int>& x){
for(int node : adj[v]){
DFS(node, adj, dp, x);
}
if(x[v] >= 0) dp[v] = 0;
else{
for(int node : adj[v]){
dp[v] = min(dp[v], dp[node]);
}
dp[v] += -x[v]; //I'm defining cost here, so it's positive. Less is better.
}
}
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, 2e18); //Min cost until profit.
for(int i = 0; i < N; i++){
if(p[i] == -1) DFS(i, adj, dp, x);
}
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";
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
135 ms |
23332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
135 ms |
23332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |