#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<int,pii>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
vector<int>adj[300005];
int arr[300005];
int dp[300005];
vector<int>storage[300005];
void merge(int a, int b){
if(storage[a].size()<storage[b].size()) swap(storage[a],storage[b]);
for(auto it:storage[b]) storage[a].push_back(it);
}
void dfs(int index){
for(auto it:adj[index]){
dfs(it);
if(dp[it]>0){
merge(index,it);
dp[index]+=dp[it];
}
}
dp[index]+=arr[index];
if((int)storage[index].size()==0){
storage[index].push_back(index);
}
}
//mini
int f(int index){
set<int>se;
for(auto it:storage[index]) se.insert(it);
priority_queue<pii>pq;
pq.push({arr[index],index});
int counter=0;
int mini=0;
while(!pq.empty()){
pii cur=pq.top();
pq.pop();
counter+=cur.first;
mini=min(mini,counter);
if(se.find(cur.second)==se.end()){
for(auto it:adj[cur.second]){
pq.push({arr[it],it});
}
}
}
return mini;
}
vector<int>rt;
void solve(){
int n,m;
cin >> n >> m;
int temp,temp2;
for(int x=1;x<=n;x++){
cin >> temp >> temp2;
swap(temp,temp2);
if(temp!=0){
adj[temp].push_back(x);
}
else rt.push_back(x);
arr[x]=temp2;
}
for(auto it:rt){
dfs(it);
}
int profit=0;
priority_queue<pii>pq;
for(auto it:rt){
pq.push({f(it),it});
}
while(!pq.empty()){
pii cur=pq.top();
pq.pop();
if(dp[cur.second]>=0&&m+cur.first>=0){
m+=dp[cur.second];
profit+=dp[cur.second];
}
else break;
for(auto it:storage[cur.second]){
for(auto child:adj[it]){
int hold=f(child);
if(hold<0) continue;
pq.push({f(child),child});
}
}
}
cout << profit;
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t=1;
//cin >> t;
//freopen("in.txt","r",stdin);
while(t--){
solve();
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
220 ms |
32592 KB |
Output is correct |
2 |
Correct |
154 ms |
32080 KB |
Output is correct |
3 |
Correct |
109 ms |
31376 KB |
Output is correct |
4 |
Correct |
124 ms |
38088 KB |
Output is correct |
5 |
Correct |
90 ms |
41156 KB |
Output is correct |
6 |
Correct |
84 ms |
27220 KB |
Output is correct |
7 |
Correct |
187 ms |
33432 KB |
Output is correct |
8 |
Correct |
113 ms |
31356 KB |
Output is correct |
9 |
Correct |
126 ms |
41064 KB |
Output is correct |
10 |
Correct |
88 ms |
41668 KB |
Output is correct |
11 |
Correct |
211 ms |
34956 KB |
Output is correct |
12 |
Correct |
159 ms |
32124 KB |
Output is correct |
13 |
Correct |
165 ms |
34068 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
19036 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
19036 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
19036 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
220 ms |
32592 KB |
Output is correct |
2 |
Correct |
154 ms |
32080 KB |
Output is correct |
3 |
Correct |
109 ms |
31376 KB |
Output is correct |
4 |
Correct |
124 ms |
38088 KB |
Output is correct |
5 |
Correct |
90 ms |
41156 KB |
Output is correct |
6 |
Correct |
84 ms |
27220 KB |
Output is correct |
7 |
Correct |
187 ms |
33432 KB |
Output is correct |
8 |
Correct |
113 ms |
31356 KB |
Output is correct |
9 |
Correct |
126 ms |
41064 KB |
Output is correct |
10 |
Correct |
88 ms |
41668 KB |
Output is correct |
11 |
Correct |
211 ms |
34956 KB |
Output is correct |
12 |
Correct |
159 ms |
32124 KB |
Output is correct |
13 |
Correct |
165 ms |
34068 KB |
Output is correct |
14 |
Incorrect |
3 ms |
19036 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |