Submission #61185

#	Time	Username	Problem	Language	Result	Execution time	Memory
61185		istlemin	Fireworks (APIO16_fireworks)	C++14	55 / 100	2063 ms	11736 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;

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

    if(e[v].size()==0) return make_tuple(multiset<ll>({0,0}),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);
        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()));


    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});
    }


    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:62: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