Submission #386055

#	Time	Username	Problem	Language	Result	Execution time	Memory
386055		Jasiekstrz	Fireworks (APIO16_fireworks)	C++17	26 / 100	15 ms	15596 KiB

fireworks

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=6e5;
int p[N+10];
int c[N+10];
int leaves[N+10];
int mx_son[N+10];
vector<pair<int,int>> e[N+10];
void count_leaves(int x)
{
	if(e[x].empty())
	{
		leaves[x]=1;
		return;
	}
	leaves[x]=0;
	mx_son[x]=0;
	for(auto v:e[x])
	{
		count_leaves(v.fi);
		if(leaves[v.fi]>leaves[mx_son[x]])
			mx_son[x]=v.fi;
		leaves[x]+=leaves[v.fi];
	}
	return;
}
void add_edge(multiset<long long> &st,int cc)
{
	if(st.empty())
	{
		st.insert(cc);
		st.insert(cc);
		return;
	}
	long long init_val[2];
	for(int i:{0,1})
	{
		init_val[i]=*prev(st.end());
		st.erase(prev(st.end()));
	}
	for(int i:{0,1})
		st.insert(init_val[i]+cc);
	return;
}
void solve(int x,multiset<long long> &st)
{
	multiset<long long> tmp;
	for(auto v:e[x])
	{
		if(v.fi==mx_son[x])
		{
			solve(v.fi,st);
			add_edge(st,v.se);
			break;
		}
	}
	for(auto v:e[x])
	{
		if(v.fi==mx_son[x])
			continue;
		tmp.clear();
		solve(v.fi,tmp);
		add_edge(tmp,v.se);
		for(auto vt:tmp)
			st.insert(vt);
	}
	while(st.size()>leaves[x]+1)
		st.erase(prev(st.end()));
	return;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,m;
	long long ans=0;
	cin>>n>>m;
	for(int i=2;i<=n+m;i++)
	{
		cin>>p[i]>>c[i];
		e[p[i]].push_back({i,c[i]});
		ans+=c[i];
	}
	count_leaves(1);
	multiset<long long> ans_set;
	solve(1,ans_set);
	int w=-m,prv=0;
	for(auto v:ans_set)
	{
		ans+=(long long)w*(v-prv);
		prv=v;
		w++;
	}
	cout<<ans<<"\n";
	return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'void solve(int, std::multiset<long long int>&)':
fireworks.cpp:69:17: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |  while(st.size()>leaves[x]+1)
      |        ~~~~~~~~~^~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 19 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45