Submission #1047712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047712		raczek	Jobs (BOI24_jobs)	C++17	0 / 100	28 ms	19912 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG 
auto& operator <<(auto& o, pair<auto, auto> p) {return o<<"{"<<p.first<<", "<<p.second<<"}";}
auto& operator <<(auto& o, auto x) {o<<"{"; for(auto v : x) o<<v<<", "; return o<<"}";}
#define debug(X) cerr<<"["#X"]: "<<X<<endl;
#else
#define debug(X) {}
#endif
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, s;
	cin>>n>>s;
	int org = s;
	vector<vector<int> > graph(n+1);
	vector<int> cost(n+1);
	vector<bool> deg(n+1, true);
	for(int i=1;i<=n;i++)
	{
		int p, c;
		cin>>c>>p;
		cost[i] = c;
		if(p == 0) deg[i] = false;
		else
		graph[p].push_back(i);
	}
	function<int(int, int, bool)> dfs = [&](int a, int bal, bool f)
	{
		bal += cost[a];
		if(bal < 0) return -1;
		vector<pair<int, int> > paths;
		paths.push_back({0, a});
		for(auto v : graph[a])
			paths.push_back({dfs(v, bal, false), v});
		sort(paths.begin(), paths.end());
		if(f) 
		{
			deg[a] = true; for(auto v : graph[a]) deg[v] = false;
			if(paths.back().second != a)
			dfs(paths.back().second, bal, true);
		}
		return paths.back().first + cost[a];
	};
	while(true)
	{
		vector<pair<int, int> > paths;
		for(int i=1;i<=n;i++) if(deg[i] == false) paths.push_back({dfs(i, s, false), i});
		sort(paths.begin(), paths.end());
		if(paths.back().first > 0) {dfs(paths.back().second, s, true); s += paths.back().first;}
		else break;
	}
	cout<<s-org;
}

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