Submission #1004676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004676		Trisanu_Das	Jobs (BOI24_jobs)	C++17	40 / 100	82 ms	58564 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
vector<long long> x;
vector<vector<int> > c;
vector<pair<long long, long long> > res;
 
long long dfs(int a) {
	long long sum = x[a];
	for(int i = 0; i < c[a].size(); i++) sum += dfs(c[a][i]);
	return max(sum, 0ll);
}
 
void dfs2(int a, long long pr, long long mp, long long lo) {
	long long nex = pr + x[a];
	if(nex > mp) res.push_back({lo - mp, nex - mp});
	for(int i = 0; i < c[a].size(); i++) dfs2(c[a][i], nex, max(mp, nex), min(lo, nex));
}
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, a; long long s;
	cin >> n >> s;
	x.resize(n + 1);
	c.resize(n + 1);
	x[0] = 0ll;
	for(int i = 1; i <= n; i++){
		cin >> x[i] >> a;
		c[a].push_back(i);
	}
	if(s == 1e18) cout << dfs(0) << '\n';
	else {
		long long ans = 0;
		for(int i = 0; i < c[0].size(); i++) dfs2(c[0][i], 0ll, 0ll, 0ll);
		sort(res.begin(), res.end(), greater<pair<long long, long long> >());
		for(int i = 0; i < res.size(); i++){
			if(res[i].first + s < 0) break;
			s += res[i].second;
			ans += res[i].second;
		}
		cout << ans << '\n';
	}
}

Compilation message (stderr)

Main.cpp: In function 'long long int dfs(int)':
Main.cpp:10:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |  for(int i = 0; i < c[a].size(); i++) sum += dfs(c[a][i]);
      |                 ~~^~~~~~~~~~~~~
Main.cpp: In function 'void dfs2(int, long long int, long long int, long long int)':
Main.cpp:17:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for(int i = 0; i < c[a].size(); i++) dfs2(c[a][i], nex, max(mp, nex), min(lo, nex));
      |                 ~~^~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for(int i = 0; i < c[0].size(); i++) dfs2(c[0][i], 0ll, 0ll, 0ll);
      |                  ~~^~~~~~~~~~~~~
Main.cpp:36:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for(int i = 0; i < res.size(); i++){
      |                  ~~^~~~~~~~~~~~

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