Submission #61189

#	Time	Username	Problem	Language	Result	Execution time	Memory
61189		istlemin	Fireworks (APIO16_fireworks)	C++14	55 / 100	2045 ms	258332 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<multiset<ll>*,ll> getCost(ll v){ //p1,p2,h

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

	multiset<ll> allPoints;

    vector<tuple<multiset<ll>,ll> > allChildcosts;

    ll slope = 0;
    ll costAllZero = 0;

    rep(i,0,e[v].size()){
		multiset<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(points->end());
        ll l2 = *prev(prev(points->end()));
        points->erase(prev(points->end()));
        points->erase(prev(points->end()));

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

        points->insert(l1);
        points->insert(l2);

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

        trav(p,*points) allPoints.insert(p);

        slope -= points->size()-1;
        costAllZero += costZero;

        /*if(v==1){
			cout<<e[v][i].first<<": "<<endl;
			cout<<"costZero: "<<costZero<<endl;
			trav(p,points){
				cout<<p<<" ";
			}
			cout<<endl;
		}*/

        //allChildcosts.emplace(points,h);
    }
    while(allPoints.size()>-slope+1)
		allPoints.erase(prev(allPoints.end()));


	ms.push_back(allPoints);
	return make_tuple(&ms[ms.size()-1],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});
    }


    multiset<ll> *points;
    ll costZero;
    tie(points,costZero) = getCost(0);

    ll last = 0;
    ll ans = 1e18;
    ll cost = costZero;
    ll slope = -(points->size()-1);
    //cout<<"costZero: "<<costZero<<endl;
    trav(p,*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<std::multiset<long long int, std::less<long long int>, std::allocator<long long int> >*, long long int> getCost(ll)':
fireworks.cpp:70:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(allPoints.size()>-slope+1)
           ~~~~~~~~~~~~~~~~^~~~~~~~~

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