Submission #933046

#	Time	Username	Problem	Language	Result	Execution time	Memory
933046		Cyber_Wolf	Magic Tree (CEOI19_magictree)	C++17	21 / 100	84 ms	33632 KiB

magictree

#include <bits/stdc++.h>

using namespace std;

#define lg long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const lg N = 1e5+5;

lg n, m, k;
lg v[N], d[N];
vector<lg> adj[N];
map<lg, lg> mp2;

void solve(lg src)
{
	map<lg, lg> mp;
	mp[0] = 0; 
	for(auto it : adj[src])
	{
		solve(it);
		if(mp.size() < mp2.size())
		{
			swap(mp, mp2);
		}
		for(auto [it, fr] : mp2)
		{
			mp[it] += fr;
		}
	}
	if(d[src])
	{
		mp[d[src]] += v[src];
		while(mp.size() > 1 && ((--mp.end())->second) <= v[src] && ((--mp.end())->first) > d[src] && v[src] >= 0)
		{
			v[src] -= ((--mp.end())->second);
			mp.erase(--mp.end());
		}
		while(mp.size() > 1 && ((--mp.end())->first) > d[src] && v[src] >= 0)
		{
			((--mp.end())->second) -= v[src];
			break;
		}
	} 
	swap(mp, mp2);
	return ;
}

int main()
{
	fastio;
	cin >> n >> m >> k;
	for(int i = 2; i <= n; i++)
	{
		lg p;
		cin >> p;
		adj[p].push_back(i);
	}
	for(int i = 1; i <= m; i++)
	{
		lg node, day, score;
		cin >> node >> day >> score;
		d[node] = day;
		v[node] = score;
	}
	solve(1);
	lg ans = 0;
	for(auto [a, b] : mp2)	ans += b;
	cout << ans << '\n';

    return 0;
}


/*
dp[src][max] = max(dp[par][v[i]]+w[i], dp[src][max-1])
*/

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