Submission #3025243

---

Source Code Expand

#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define FASTIO
#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

#ifdef FASTIO
#define scanf abacaba
#define printf abacaba
#endif

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;


/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/

const int MAXN = 55;

int n;
ll x, d;
ll m[MAXN];
int p[MAXN];
int sz[MAXN];

const int MX = 150000;
array<ll, MX> dp;
int lst[MAXN];

int main() {
#ifdef FASTIO
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#endif
	cin >> n >> x >> d;
	cin >> m[0];
	for (int i = 1; i < n; ++i) {
		cin >> m[i] >> p[i];
		--p[i];
	}
	for (int i = n - 1; i >= 0; --i) {
		sz[i] += 1;
		m[p[i]] += m[i];
		sz[p[i]] += sz[i];
	}
	vector<array<ll, 3>> vv;
	vv.push_back({m[0], sz[0], x});
	for (int i = 1; i < n; ++i)
		vv.push_back({m[i], sz[i], d});
	sort(vv.begin(), vv.end(), [] (array<ll, 3> a, array<ll, 3> b) {
			return a[0] * b[1] < a[1] * b[0];
			});

	ll add = 0;
	for (int i = 0; i < vv.size(); ++i) {
		if (vv[i][2] <= n)
			continue;
		ll lf = x;
		for (int j = 0; j < i; ++j) {
			lf -= vv[j][0] * vv[j][2];
			if (lf < 0)
				break;
		}
		for (int j = i + 1; j < vv.size() && lf >= 0; ++j) {
			int k = 0;
			while ((k + 1) * vv[j][0] / vv[i][0] * vv[i][1] < (k + 1) * vv[j][1])
				++k;
			lf -= vv[j][0] * k;
		}
		if (lf >= 0) {
			ll go = min(vv[i][2] - n, lf / vv[i][0]);
			add += vv[i][1] * go;
			x -= vv[i][0] * go;
			lf -= vv[i][0] * go;
			vv[i][2] -= go;
			if (vv[i][2] > n)
				break;
		}
		else {
			break;
		}
	}
	dp.fill(x + 1);
	dp[0] = 0;
	for (int i = 0; i < vv.size(); ++i) {
		int n = vv[i][1];
		ll cs = vv[i][0];
		ll av = vv[i][2];
		for (int j = 0; j < n; ++j)
			lst[j] = j;
		auto dp2 = dp;
		for (int i = 0; i < MX; ++i) {
			int g = i % n;
			if (lst[g] <= i)
				lst[g] = i + n;
			int k = (lst[g] - i) / n;
			for (; lst[g] < MX && k <= av; lst[g] += n, ++k) {
				if (dp2[lst[g]] > dp[i] + cs * k)
					dp2[lst[g]] = dp[i] + cs * k;
				else
					break;
			}
		}
		dp = dp2;
	}
	ll ans = add;
	for (int i = 0; i < MX; ++i)
		if (dp[i] <= x)
			ans = max(ans, add + i);
	cout << ans << "\n";
	return 0;
}

Submission Info

Judge Result