Submission #933027

#	Time	Username	Problem	Language	Result	Execution time	Memory
933027		Cyber_Wolf	Magic Tree (CEOI19_magictree)	C++17	3 / 100	81 ms	16212 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;

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

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;
	}
	cout << solve(1) << '\n';

    return 0;
}


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

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