Submission #1231559

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231559		vuavisao	Magic Tree (CEOI19_magictree)	C++20	3 / 100	101 ms	40384 KiB

magictree

#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

using ll = long long;

const int N = 100'000 + 10;
const ll INF = 1'000'000'000'000'000'000;

int n_nodes, cnt_fruits, max_day;
vector<int> g[N];

bool have_fruit[N];
int day[N], cost[N];
vector<int> nearest[N];
multiset<pair<int, ll>> mst[N];

ll dp[N];

void dfs(int u) {
	for (const auto& v : g[u]) {
		dfs(v);
	}

	int big_child_nearest = u;
	for (const auto& v : g[u]) {
		if ((int) nearest[v].size() > (int) nearest[big_child_nearest].size()) big_child_nearest = v;
	}
	swap(nearest[u], nearest[big_child_nearest]);
	for (const auto& v : g[u]) {
		for (const auto& v2 : nearest[v]) nearest[u].push_back(v);
	}

	if (have_fruit[u]) {
		ll new_no_use = 0;
		dp[u] = cost[u];
		for (const auto& v : nearest[u]) {
			ll add = 0;
			// if (u == 1) {
			// 	cerr << "IN: " << v << ' ' << mst[v].size() << '\n';
			// }
			auto last = mst[v].upper_bound(make_pair(day[u], INF));
			if (last != mst[v].begin()) {
				// if (u == 1) {
				// 	for (auto ptr = mst[v].begin(); ptr != last; ptr = next(ptr)) cerr << "GET:" << ptr->second << '\n';
				// }
				for (auto ptr = mst[v].begin(); ptr != last; ptr = next(ptr)) add += ptr->second;
				mst[v].erase(mst[v].begin(), last);
			}
			dp[u] += max(add, (day[u] >= day[v] ? dp[v] : 0ll));
			new_no_use += add;
		}
		nearest[u].clear();
		nearest[u].push_back(u);
		if (g[u].empty()) {
			new_no_use += cost[u];
		}
		if (new_no_use > 0) {
			// cerr << "USE: " << u << ' ' << new_no_use << '\n';
			mst[u].insert(make_pair(day[u], new_no_use));
		}
	}

	int big_child_mst = u;
	for (const auto& v : g[u]) {
		if ((int) mst[v].size() > (int) mst[big_child_mst].size()) big_child_mst = v;
	}
	swap(mst[u], mst[big_child_mst]);
	for (const auto& v : g[u]) {
		mst[u].insert(mst[v].begin(), mst[v].end());
	}
}

int32_t main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr); std::cout.tie(nullptr);
	cin >> n_nodes >> cnt_fruits >> max_day;
	for (int v = 2; v <= n_nodes; ++v) {
		int u; cin >> u;
		g[u].push_back(v);
		// cerr << u << ' ' << v << '\n';
	}
	for (int i = 1; i <= cnt_fruits; ++i) {
		int u; cin >> u;
		have_fruit[u] = true;
		cin >> day[u] >> cost[u];
	}
	have_fruit[1] = true;
	day[1] = 1'000'000'000;
	dfs(1);
	// cerr << "DP:\n";
	// for (int u = 1; u <= n_nodes; ++u) cerr << u << ' ' << dp[u] << '\n';
	cout << *max_element(dp + 1, dp + 1 + n_nodes);
	return (0 ^ 0);
}

/// Code by vuavisao

• Subtask 1: 0 / 6
• Subtask 2: 3 / 3
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 16
• Subtask 6: 0 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17