oj.uz

Submission #994616

# Submission time Handle Problem Language Result Execution time Memory
994616 2024-06-08T02:32:23 Z LCJLY Jobs (BOI24_jobs) C++14
11 / 100
 220 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 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();
	}
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory 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

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 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 -