oj.uz

Submission #994624

# Submission time Handle Problem Language Result Execution time Memory
994624 2024-06-08T02:37:06 Z LCJLY Jobs (BOI24_jobs) C++14
11 / 100
 207 ms 41668 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 continue;
		for(auto it:storage[cur.second]){
			for(auto child:adj[it]){
				int hold=f(child); 
				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();
	}
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 32592 KB Output is correct
2 Correct 144 ms 31684 KB Output is correct
3 Correct 106 ms 31360 KB Output is correct
4 Correct 120 ms 38088 KB Output is correct
5 Correct 86 ms 41356 KB Output is correct
6 Correct 78 ms 27220 KB Output is correct
7 Correct 197 ms 33468 KB Output is correct
8 Correct 123 ms 31448 KB Output is correct
9 Correct 112 ms 41044 KB Output is correct
10 Correct 83 ms 41668 KB Output is correct
11 Correct 207 ms 34960 KB Output is correct
12 Correct 153 ms 32112 KB Output is correct
13 Correct 203 ms 34200 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 19032 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 19032 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 19032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 32592 KB Output is correct
2 Correct 144 ms 31684 KB Output is correct
3 Correct 106 ms 31360 KB Output is correct
4 Correct 120 ms 38088 KB Output is correct
5 Correct 86 ms 41356 KB Output is correct
6 Correct 78 ms 27220 KB Output is correct
7 Correct 197 ms 33468 KB Output is correct
8 Correct 123 ms 31448 KB Output is correct
9 Correct 112 ms 41044 KB Output is correct
10 Correct 83 ms 41668 KB Output is correct
11 Correct 207 ms 34960 KB Output is correct
12 Correct 153 ms 32112 KB Output is correct
13 Correct 203 ms 34200 KB Output is correct
14 Incorrect 3 ms 19032 KB Output isn't correct
15 Halted 0 ms 0 KB -