Submission #1086553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086553		IBory	Jobs (BOI24_jobs)	C++17	14 / 100	2027 ms	35152 KiB

Main

#include <bits/stdc++.h>
#define pii pair<ll, ll>
typedef long long ll;
using namespace std;

const int MAX = 300003;
set<int> G[MAX];
ll S[MAX], P[MAX], V[MAX];

void PDFS(int cur) {
	vector<int> C;
	for (int next : G[cur]) {
		PDFS(next);
		if (S[next] >= 0) C.push_back(next);
	}

	for (int i = 1; i < C.size(); ++i) {
		if (G[C[0]].size() < G[C[i]].size()) {
			swap(S[C[0]], S[C[i]]);
			swap(G[C[0]], G[C[i]]);
		}
		S[C[0]] += S[C[i]]; S[C[i]] = 0;
		for (int next : G[C[i]]) {
			P[next] = C[0];
			G[C[0]].insert(next);
		}
		G[C[i]].clear();
		G[cur].erase(C[i]);
	}

	// if (1 < C.size()) {
	// 	cout << "Move Res.\n";
	// 	cout << cur << ' ' << S[cur] << ' ' << S[*G[cur].begin()] << '\n';
	// 	for (int n : G[cur]) cout << n << ' ';
	// 	cout << '\n' << '\n';
	// }
}

pii DFS(int cur, ll lim, ll down, ll up) {
	pii ret = {-1, cur};
	if (!V[cur] && -down <= lim) ret = max(ret, pii{up, cur});
	for (int next : G[cur]) {
		ret = max(ret, DFS(next, lim, min(down, up + S[next]), up + S[next]));
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	ll N, init;
	cin >> N >> init;
	for (int i = 1; i <= N; ++i) {
		cin >> S[i] >> P[i];
		G[P[i]].insert(i);
	}

	PDFS(0);

	V[0] = 1;
	ll ans = init, cnt = 0;
	while (1) {
		auto [val, cur] = DFS(0, ans, 0, S[0]);
		if (val < 0) break;

		ans += val;
		while (cur && !V[cur]) {
			V[cur] = 1;
			S[cur] = 0;
			cur = P[cur];
		}
	}

	cout << ans - init;
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void PDFS(int)':
Main.cpp:17:20: 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 = 1; i < C.size(); ++i) {
      |                  ~~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:60:17: warning: unused variable 'cnt' [-Wunused-variable]
   60 |  ll ans = init, cnt = 0;
      |                 ^~~

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