oj.uz

Submission #994615

# Submission time Handle Problem Language Result Execution time Memory
994615 2024-06-08T02:29:50 Z LCJLY Jobs (BOI24_jobs) C++14
0 / 100
 190 ms 32592 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){
		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]){
				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();
	}
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 32592 KB Output is correct
2 Incorrect 157 ms 31912 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 19036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 19036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 19036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 32592 KB Output is correct
2 Incorrect 157 ms 31912 KB Output isn't correct
3 Halted 0 ms 0 KB -