Submission #228507

#TimeUsernameProblemLanguageResultExecution timeMemory
228507oolimryMagic Tree (CEOI19_magictree)C++14
100 / 100
172 ms37752 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...