Submission #793179

#	Time	Username	Problem	Language	Result	Execution time	Memory
793179		algorithm16	Fireworks (APIO16_fireworks)	C++14	7 / 100	4 ms	7376 KiB

fireworks

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long int llint;
vector <pair<int,int> > v[300005];
vector <llint> v1,sum;
pair <llint,llint> dp[300005];
llint calc(llint l) {
	if(v1.empty()) return 0;
	llint idx=lower_bound(v1.begin(),v1.end(),l+1)-v1.begin();
	llint ret=idx*l-(v1.size()-idx)*l;
	ret+=sum[v1.size()-1];
	if(idx) ret-=2*sum[idx-1];
	return ret;
}
llint find_l() {
	if(v1.empty()) return 0;
	llint lo=0,hi=1e18;
	while(lo<hi) {
		llint mid=(lo+hi)/2;
		if(calc(mid)<calc(mid+1)) hi=mid;
		else lo=mid+1;
	}
	return lo;
}
void rec(int x) {
	llint ret=0,l=0;
	v1.clear();
	sum.clear();
	for(int i=0;i<v[x].size();i++) {
		rec(v[x][i].first);
	}
	for(int i=0;i<v[x].size();i++) {
		ret+=dp[v[x][i].first].first;
		v1.push_back(v[x][i].second+dp[v[x][i].first].second);
	}
	sort(v1.begin(),v1.end());
	llint sum1=0;
	for(int i=0;i<v1.size();i++) {
		sum1+=v1[i];
		sum.push_back(sum1);
	}
	l=find_l();
	ret+=calc(l);
	dp[x]=make_pair(ret,l);
	//cout << x << "  " << ret << " " << l << "\n";
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n,m;
	cin >> n >> m;
	for(int i=1;i<n+m;i++) {
		int x,c;
		cin >> x >> c;
		v[x-1].push_back(make_pair(i,c));
	}
	rec(0);
	cout << dp[0].first;
	return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'void rec(int)':
fireworks.cpp:31:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int i=0;i<v[x].size();i++) {
      |              ~^~~~~~~~~~~~
fireworks.cpp:34:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for(int i=0;i<v[x].size();i++) {
      |              ~^~~~~~~~~~~~
fireworks.cpp:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i=0;i<v1.size();i++) {
      |              ~^~~~~~~~~~

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