Submission #1301415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301415		XXBabaProBerkay	Jobs (BOI24_jobs)	C++20	0 / 100	35 ms	3896 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define MP make_pair
#define PB push_back
#define all(x) begin(x), end(x)

using ll = long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using str = string;

template<typename T>
using vec = vector<T>;

template<typename T, size_t N>
using arr = array<T, N>;

const ll INF = 1e17;
const int MOD = 1e9 + 7;

int N;
ll s;
vec<int> x, p;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> s;
	x = p = vec<int>(N + 1);
	vec<int> nxt(N + 1);
	priority_queue<pi> PQ;
	for (int i = 1; i <= N; i++) {
		cin >> x[i] >> p[i];
		if (!p[i]) PQ.push(MP(x[i], i));
		else nxt[p[i]] = i;
	}

	ll ans = 0, res = 0;
	while (!PQ.empty()) {
		int d, u;
		tie(d, u) = PQ.top();
		PQ.pop();

		if (INF - s < d) s = INF;
		else s += d;

		res += d;
		ans = max(ans, res);

		if (s < 0) break;
		if (nxt[u] == 0) continue;

		int v = nxt[u];
		PQ.push(MP(x[v], v));
	}

	cout << ans << '\n';
}

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