Submission #1047839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047839		raczek	Jobs (BOI24_jobs)	C++17	14 / 100	2064 ms	19028 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
#define int long long
const int INF = 1e18;
int32_t 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)> dfs = [&](int a, int bal)
	{
		bal += cost[a];
		if(bal >= s) 
		{
			deg[a] = true;
			for(auto v : graph[a]) deg[v] = false;
			return cost[a];
		}
		if(bal < 0) return -INF;
		for(auto v : graph[a])
		{
			int c = dfs(v, bal);
			if(c > -INF) 
			{
				deg[a] = true;
				for(auto u : graph[a]) 
					if(u != v)
						deg[u] = false;
				return c + cost[a];
			}
		}
		return -INF;
	};
	while(true)
	{
		int f = false;
		for(int i=1;i<=n;i++) if(deg[i] == false) {int x = dfs(i, s); if(x >= 0) {s += x; f = 1; break;}}
		if(!f) break;
	}
	cout<<s-org;
}

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