Submission #228507

#	Time	Username	Problem	Language	Result	Execution time	Memory
228507		oolimry	Magic Tree (CEOI19_magictree)	C++14	100 / 100	172 ms	37752 KiB

magictree

#include <bits/stdc++.h>
#define day first
#define value second
using namespace std;

typedef pair<int, long long> ii;
ii fruit[100005];
map<int, long long> dp[100005];
vector<int> adj[100005];

void dfs(int u){
	auto& cur = dp[u]; ///updating cur updates dp[u]
	
	for(int v : adj[u]){
		dfs(v);
		if(cur.size() < dp[v].size()) swap(cur, dp[v]);
		for(ii x : dp[v]) cur[x.day] += x.value;
	}
	
	ii F = fruit[u];
	if(fruit[u] == ii(0,0)) return;
	
	cur[F.day] += F.value;
	long long subtract = F.value;
	while(true){
		auto it = cur.find(F.day); it++;
		if(it == cur.end()) break;
		if(it->second > subtract){
			it->second -= subtract;
			break;
		}
		subtract -= it->second;
		dp[u].erase(it);
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.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);
	}
	
	while(m--){
		int u; cin >> u;
		cin >> fruit[u].day >> fruit[u].value;
	}
	
	dfs(1);
	long long ans = 0;
	for(ii x : dp[1]) ans += x.value;
	cout << ans;
}

• 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