Submission #61197

#	Time	Username	Problem	Language	Result	Execution time	Memory
61197		istlemin	Fireworks (APIO16_fireworks)	C++14	100 / 100	1101 ms	172120 KiB

fireworks

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

vector<vector<pii> > e;

vector<multiset<ll>> ms;

tuple<ll,ll> getCost(ll v){ //p1,p2,h

    if(e[v].size()==0) {
		ms.push_back(multiset<ll>({0,0}));
		return make_tuple(ms.size()-1,0);
    }
    //ll slope = 0;
   // vector<pii> events;

	ll allPoints;

    vector<ll> allChildpoints;

    ll slope = 0;
    ll costAllZero = 0;

    rep(i,0,e[v].size()){
		ll points;
		ll costZero;
        tie(points,costZero) = getCost(e[v][i].first);
        //cout<<e[v][i].first<<": "<<endl;
        //cout<<ms[ms.size()-1].size()<<endl;
        //cout<<points->size()<<endl;
        ll l1 = *prev(ms[points].end());
        ll l2 = *prev(prev(ms[points].end()));
        ms[points].erase(prev(ms[points].end()));
        ms[points].erase(prev(ms[points].end()));

        l1+=e[v][i].second;
        l2+=e[v][i].second;

        ms[points].insert(l1);
        ms[points].insert(l2);

        costZero += e[v][i].second;

        slope -= ms[points].size()-1;
        costAllZero += costZero;

        allChildpoints.push_back(points);
        /*cout<<"A"<<e[v][i].first<<endl;
        cout<<allChildpoints.size()<<endl;
		rep(i,0,allChildpoints.size()){
			cout<<i<<": "<<endl;
			cout<<ms[allChildpoints[0]].size()<<endl;
		}*/
        /*if(v==1){
			cout<<e[v][i].first<<": "<<endl;
			cout<<"costZero: "<<costZero<<endl;
			trav(p,points){
				cout<<p<<" ";
			}
			cout<<endl;
		}*/

        //allChildcosts.emplace(points,h);
    }

	ll mx = 0;
    ll mxIndex = 0;
    rep(i,0,allChildpoints.size()){
		//cout<<i<<" "<<endl;
		//cout<<allChildpoints.size()<<" "<<endl;
		//cout<<ms[allChildpoints[i]].size()<<endl;
        if(ms[allChildpoints[i]].size()>mx){
			mx = ms[allChildpoints[i]].size();
            mxIndex = i;
        }
    }

    allPoints = allChildpoints[mxIndex];

    rep(i,0,allChildpoints.size()){
		if(i==mxIndex) continue;
		trav(p,ms[allChildpoints[i]]) ms[allPoints].insert(p);
    }

    while(ms[allPoints].size()>-slope+1)
		ms[allPoints].erase(prev(ms[allPoints].end()));


	return make_tuple(allPoints,costAllZero);
}

int main(){
	cin.sync_with_stdio(false);
	ll n,m;
	cin>>n>>m;
    n+=m;
    e.resize(n);
    rep(i,1,n){
        ll a = i;
        ll b,c; cin>>b>>c;
        e[b-1].push_back({a,c});
    }


    ll points;
    ll costZero;
    tie(points,costZero) = getCost(0);

    ll last = 0;
    ll ans = 1e18;
    ll cost = costZero;
    ll slope = -(ms[points].size()-1);
    //cout<<"costZero: "<<costZero<<endl;
    trav(p,ms[points]){
		//cout<<p<<" ";
        cost += slope*(p-last);
        ans = min(ans,cost);
        slope++;
        last = p;
    }
    //cout<<endl;
    cout<<ans<<endl;
}

Compilation message (stderr)

fireworks.cpp: In function 'std::tuple<long long int, long long int> getCost(ll)':
fireworks.cpp:82:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(ms[allChildpoints[i]].size()>mx){
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
fireworks.cpp:95:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ms[allPoints].size()>-slope+1)
           ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~

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