Submission #654103

#	Time	Username	Problem	Language	Result	Execution time	Memory
654103		dutinmeow	Magic Tree (CEOI19_magictree)	C++17	100 / 100	247 ms	40220 KiB

magictree

#include <bits/stdc++.h>

int main() {
	using namespace std;

	int N, M, K;
	cin >> N >> M >> K;
	vector<int> P(N + 1);
	for (int i = 2; i <= N; i++) 
		cin >> P[i];
	vector<int> D(N + 1, -1);
	vector<long long> W(N + 1);
	for (int i = 0; i < M; i++) {
		int u, d;
		long long w;
		cin >> u >> d >> w;
		tie(D[u], W[u]) = make_pair(d, w);
	}

	vector<map<int, long long>> A(N + 1);
	for (int i = N; i > 1; i--) {
		if (D[i] != -1) {
			auto it = A[i].emplace(D[i], 0).first;
			it->second += W[i];
			for (it = next(it); 
				it != A[i].end() && W[i] >= it->second; 
				W[i] -= it->second, it = A[i].erase(it)
			);
			if (it != A[i].end())
				it->second -= W[i];
		}
		if (A[i].size() > A[P[i]].size())
			swap(A[i], A[P[i]]);
		for (auto [k, v] : A[i])
			A[P[i]][k] += v;
	}	
	long long ans = 0;
	for (auto [k, v] : A[1])
		ans += v;
	cout << ans << '\n';
}

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