Submission #287491

#	Time	Username	Problem	Language	Result	Execution time	Memory
287491		dlwocks31	Magic Tree (CEOI19_magictree)	C++17	58 / 100	344 ms	34296 KiB

magictree

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MX = 1e5+1;
vector<int> adj[MX];
pair<int, int> fruit[MX];
multiset<pair<int, int>> ms[MX];
void merge(multiset<pair<int, int>>& st, pair<int, int> pr) {
	auto [d, w] = pr;
	auto it = st.lower_bound(make_pair(d+1, -1));
	while(w > 0 && it != st.end()) {
		if(w >= it->second) {
			it = st.erase(it);
			w -= it->second;
		} else {
			st.insert({it->first, it->second - w});
			st.erase(it);
			w = 0;
		}
	}
	st.insert(pr);
}
void dfs(int i, int p) {
	int leaf = 1;
	for(int a: adj[i]) {
		if(a == p) continue;
		leaf = 0;
		dfs(a, i);
	}
	if(leaf) {
		if(fruit[i].first)
			ms[i] = {fruit[i]};
	} else {
		int mx = 0;
		for(int a: adj[i]) {
			if(a == p) continue;
			if(ms[a].size() > ms[mx].size())
				mx = a;
		}
		ms[i] = move(ms[mx]);
		for(int a: adj[i]) {
			if(a == p || a == mx) continue;
			for(auto pr: ms[a]) {
				ms[i].insert(pr);
			}
			ms[a].clear();
		}
		if(fruit[i].first) 
			merge(ms[i], fruit[i]);
	}

}
int32_t main() {
	//ios::sync_with_stdio(0);cin.tie(0);
	int n, m, k;
	cin >> n >> m >> k;
	for(int i=2; i<=n; i++) {
		int p;
		cin >> p;
		adj[p].push_back(i);
		adj[i].push_back(p);
	}
	for(int i=0; i<m; i++) {
		int v, d, w;
		cin >> v >> d >> w;
		fruit[v] = {d, w};
	}
	dfs(1, 0);
	int ans = 0;
	for(auto [d, w]: ms[1]) {
		ans += w;
	}
	cout << ans;
}

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