Submission #932911

#	Time	Username	Problem	Language	Result	Execution time	Memory
932911		beepbeepsheep	Magic Tree (CEOI19_magictree)	C++17	16 / 100	104 ms	41044 KiB

magictree

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>

const ll maxn=1e5+5;
const ll inf=1e15; 

vector<ll> adj[maxn];
set<ii> s[maxn];
ii arr[maxn];

void dfs(ll x){
	for (auto u:adj[x]){
		dfs(u);
		if (s[u].size()>s[x].size()) swap(s[u],s[x]);
		for (auto [a,b]:s[u]) s[x].emplace(a,b);
	}
	ll pos,cnt;
	tie(pos,cnt)=arr[x];
	while (cnt){
		ll p,c;
		if (s[x].lower_bound(make_pair(pos,-1))==s[x].end()) break;
		tie(p,c)=*s[x].lower_bound(make_pair(pos,-1));
		if (cnt>=c){
			cnt-=c;
			s[x].erase(make_pair(p,c));
		} else{
			s[x].erase(make_pair(p,c));
			c-=cnt;
			cnt=0;
			s[x].emplace(p,c);
		}
	}
	s[x].emplace(arr[x]);
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll n,k,m,a,b,c;
	cin>>n>>k>>m;
	for (int i=2;i<=n;i++){
		cin>>a;
		adj[a].emplace_back(i);
	}
	for (int i=1;i<=k;i++){
		cin>>a>>b>>c; //pos, time, value
		arr[a]={b,c};
	}
	dfs(1);
	ll ans=0;
	for (auto [u,v]:s[1]) ans+=v;
	cout<<ans; 
	return 0;
}

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