# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
994617 |
2024-06-08T02:33:26 Z |
LCJLY |
Jobs (BOI24_jobs) |
C++14 |
|
164 ms |
32616 KB |
#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){
int hold=f(it);
if(hold<0) continue;
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({hold,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();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
164 ms |
32616 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
19032 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
19032 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
19032 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
164 ms |
32616 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |