Submission #387053

#	Time	Username	Problem	Language	Result	Execution time	Memory
387053		ogibogi2004	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	14 / 100	2086 ms	59884 KiB

worst_reporter2

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=2e5+6;
int n;
vector<int>g[MAXN];
ll c[MAXN];
int a[MAXN],h[MAXN],subtree[MAXN];
void dfs1(int u,int p)
{
	subtree[u]=1;
	for(auto xd:g[u])
	{
		if(xd==p)continue;
		dfs1(xd,u);
		subtree[u]+=subtree[xd];
	}
}
void dfs(int u,int p,map<int,ll> &mp)
{
	int bc=-1,maxst=-1;
	for(auto xd:g[u])
	{
		if(xd==p)continue;
		if(subtree[xd]>maxst)
		{
			maxst=subtree[xd];
			bc=xd;
		}
	}
	if(bc==-1)
	{
		mp[h[u]+1]=c[u];
		return;
	}
	dfs(bc,u,mp);
	for(auto xd:g[u])
	{
		if(xd==p||xd==bc)continue;
		map<int,ll> tmp;
		dfs(xd,u,tmp);
		for(auto it:tmp)
		{
			mp[it.first]+=it.second;
		}
	}
	mp[h[u]+1]+=c[u];
	mp[0]+=c[u];
	mp[h[u]]-=c[u];
	auto it=mp.lower_bound(h[u]);
	while(mp[h[u]]<0)
	{
		it--;
		int t=(*it).first;
		if(mp[t]+mp[h[u]]>=0)
		{
			mp[t]+=mp[h[u]];
			mp[h[u]]=0;
		}
		else
		{
			mp[h[u]]+=mp[t];
			mp[t]=0;
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		cin>>a[i]>>h[i]>>c[i];
		if(i!=1)g[a[i]].push_back(i);
	}
	dfs1(1,0);
	map<int,ll>mp;
	dfs(1,0,mp);
	cout<<mp[0]<<endl;
return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 65
• Subtask 3: 0 / 21