Submission #1004651

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004651		Trisanu_Das	Jobs (BOI24_jobs)	C++17	29 / 100	165 ms	59096 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 314159;
int pr[300005];
bool vis[300005];
vector<int> adj[300005];
vector<pair<int,int> > op;

void dfs(int x, int prof, int maxProf, int loss) {
	vis[x] = 1;
	if(prof + pr[x] > maxProf) op.push_back({loss - maxProf, prof + pr[x] - maxProf});
	for(auto i: adj[x]) dfs(i, prof + pr[x], max(maxProf, prof + pr[x]), min(loss, prof + pr[x]));
}

signed main() {
	int n, s, ans = 0; cin >> n >> s;
	for(int i = 1,p; i <= n; i++) {
      cin >> pr[i] >> p; 
      adj[p].push_back(i);
    }
	for(int i = 1; i <= n; i++) if(!vis[i]) dfs(i, 0, 0, 0);
	sort(op.begin(), op.end(), greater<pair<int, int> >());
	for(int i = 0; i < op.size() && op[i].first + s >= 0; i++) s += op[i].second, ans += op[i].second;
	cout << ans << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:24:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(int i = 0; i < op.size() && op[i].first + s >= 0; i++) s += op[i].second, ans += op[i].second;
      |                 ~~^~~~~~~~~~~

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