oj.uz

Submission #387056

# Submission time Handle Problem Language Result Execution time Memory
387056 2021-04-07T21:41:43 Z ogibogi2004 Worst Reporter 4 (JOI21_worst_reporter4) C++14
0 / 100
 12 ms 5484 KB 
#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,int> &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,int> tmp;
		dfs(xd,u,tmp);
		for(auto it:tmp)
		{
			if(it.second!=0)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,int>mp;
	dfs(1,0,mp);
	cout<<mp[0]<<endl;
return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 5 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Incorrect 12 ms 5484 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 5356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 5 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Incorrect 12 ms 5484 KB Output isn't correct
6 Halted 0 ms 0 KB -