Submission #1266234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266234		herominhsteve	Jobs (BOI24_jobs)	C++20	100 / 100	150 ms	40904 KiB

Main

#include <bits/stdc++.h>
#define el '\n'
#define FNAME "jobs"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9+7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}

void setup(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	if (fopen(FNAME".inp","r")){
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

const int MAXN = 3e5 + 5;
const long long INF = (long long) 2e18 + 15092007;

int n;
long long S;
vector<pair<long long,int>> input;
vector<long long> w;
bool isLine=1;

void init(){
	cin>>n>>S;
	w.assign(n+1,0);
	input.resize(n+1);
	for (int i=1;i<=n;i++){
		int x;
		cin>>w[i]>>x;
		if (x and x!=i-1) isLine=0;
		input[i] = make_pair(w[i],x);
	}
}

namespace Line{
	vector<vector<long long>> chains;
	int numChains;
	void constructChains(){
		vector<long long> curChain;
		for (int i=1;i<=n;i++){
			if (!input[i].second and !curChain.empty()){
				chains.push_back(curChain);
				curChain.clear();
			}
			curChain.push_back({input[i].first});
		}
		if (!curChain.empty()) chains.push_back(curChain);
		numChains = chains.size();
	}
	
	struct Chain{
		long long req;
		long long gain;
		int ID;
		Chain(long long r,long long g,int id): req(r),gain(g),ID(id) {}
		bool operator < (const Chain &other) const{
			return req > other.req;
		}
	};

	priority_queue<Chain> pq;
	vector<int> ptr;
	
	bool getNextSegment(int ID,long long &req,long long &gain){
		long long minPre = INF;
		long long pre = 0;
		for (int &cid = ptr[ID];cid < (int)chains[ID].size();cid++){
			pre += chains[ID][cid];
			minimize(minPre,pre);
			if (pre>=0){
				req = max(0ll, -minPre);
				gain = pre;
				cid++;
				return true;
			}
		}
		return false;
	}

	void prepareRequirement(){
		for (int i=0;i<numChains;i++){
			long long req,gain;
			if (getNextSegment(i,req,gain)){
				pq.emplace(req,gain,i);
			}
		}
	}

	void solve(){
		constructChains();
		ptr.assign(numChains,0);
		prepareRequirement();
		long long totalGain=0;
		while (!pq.empty()){
			long long req = pq.top().req;
			long long gain = pq.top().gain;
			int ID = pq.top().ID;
			pq.pop();
			if (S + totalGain < req) break;
			else{
				totalGain += gain;
				if (getNextSegment(ID,req,gain)){
					pq.emplace(req,gain,ID);
				}
			}
		}
		cout<<totalGain;
		exit(0);
	}
};

namespace SubFinal{
	vector<vector<int>> graph;
	void constructTree(){
		graph.resize(n+1);
		for (int i=1;i<=n;i++){
			graph[input[i].second].push_back(i);
		}
	}

	struct Chain{
		long long req,sum;
		Chain(long long r,long long s): req(r), sum(s) {}
		bool operator < (const Chain &other) const{
			return req > other.req;
		}
	};

	void merge(priority_queue<Chain> &large, priority_queue<Chain> &smol){
		if (smol.size() > large.size()) large.swap(smol);
		while (!smol.empty()){
			large.emplace(smol.top());
			smol.pop();
		}
	}

	void combine(priority_queue<Chain> &large, Chain parent){
		while (!large.empty()){
			Chain top = large.top();
			if (parent.sum <= 0){
				large.pop();
				long long newReq = max(parent.req,top.req - parent.sum);
				parent = Chain(newReq,parent.sum + top.sum);
			} else{
				if (parent.req > top.req){
					large.pop();
					parent = Chain(parent.req,parent.sum + top.sum);
				} else{
					large.emplace(parent);
					break;
				}
			}
		}
		if (large.empty()) large.emplace(parent);
		if (large.size()==1 and large.top().sum <= 0) large.pop();
	}

	void dfs(int u,priority_queue<Chain> &large){
		for (int v : graph[u]){
			priority_queue<Chain> smol;
			dfs(v,smol);
			merge(large,smol);
		}
		combine(large,Chain(max(0ll,-w[u]),w[u]));
	}

	void solve(){
		constructTree();
		priority_queue<Chain> finalChain;
		dfs(0,finalChain);

		long long totalGain=0;
		while (!finalChain.empty()){
			long long req = finalChain.top().req;
			long long sum = finalChain.top().sum;
			finalChain.pop();
			if (S + totalGain >= req){
				totalGain += sum;
			}
		}

		cout<<totalGain;
		exit(0);
	}	
};

void sol(){
	if (isLine) Line::solve();
	SubFinal::solve();
}

int main(){
    setup();
    init();
    sol();
}

Compilation message (stderr)

Main.cpp: In function 'void setup()':
Main.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 29 / 29
• Subtask 5: 31 / 31