Submission #470465

#	Time	Username	Problem	Language	Result	Execution time	Memory
470465		humbertoyusta	Fireworks (APIO16_fireworks)	C++14	100 / 100	552 ms	148420 KiB

fireworks

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline","03") // Pragma, Optimization flags
#define db(x) cerr << #x << ": " << (x) << '\n';
#define f first
#define s second
typedef long double ld;
typedef long long ll;
/// Constraints----------------------------------------------
const int maxn = 600010;
const int mod2 = 1000000007;
const int mod = 998244353;
const ld eps = 1e-9;
const ll INF = 1ll * mod * mod;
/// Quick Functions------------------------------------------
int qpow(int b,int e){
    if( !e ) return 1;
    if( e & 1 ) return 1ll * qpow(b,e-1) * b % mod;
    int pwur = qpow(b,e>>1);
    return 1ll * pwur * pwur % mod;
}
mt19937_64 random_(time(0));
int rng (int a, int b){
    return uniform_int_distribution<int>(a,b)(random_);
}
/// Code-----------------------------------------------------

struct plf{
    ll m0, n0, offset;
    multiset<ll> s;
    plf(){
        m0 = n0 = offset = 0;
        s.clear();
    }
};

int p[maxn], pedge[maxn];
vector<pair<int,int>> g[maxn];
int n, m;
plf dp[maxn];

ll getmin(int x){
    ll curr = dp[x].m0 * (*dp[x].s.begin()+dp[x].offset) + dp[x].n0;
    ll ans = INF;
    //if( (*dp[x].s.begin()) + dp[x].offset >= 0 )
        ans = min( ans , curr );

    vector<ll> v;
    for( auto i : dp[x].s )
        v.push_back(i);

//    db(dp[x].m0)
//    db(dp[x].n0)
//    db(v[0])
    for(int i=1; i<v.size(); i++){
//        if( v[i] > 0 && v[i-1] <= 0 ){
//            ans = min( ans , curr + ( dp[x].m0 + ( i ) ) * ( 0 - v[i-1] ) );
//        }
        curr = curr + ( dp[x].m0 + ( i ) ) * ( v[i] - v[i-1] );
//        db(v[i])
        //if( v[i] + dp[x].offset >= 0 )
            ans = min( ans , curr );
    }

    return ans;
}

void dfs(int u){

    dp[u] = plf();

    if( g[u].size() == 0 ) return;

    for( auto v : g[u] ){

        dfs(v.f);

        if( v.f > n ){
            dp[v.f].m0 = -1;
            dp[v.f].n0 = 0;
            dp[v.f].s.insert(0);
            dp[v.f].s.insert(0);

            //cout << v.f << ' ' << getmin(v.f) << '\n';
        }

        dp[v.f].offset += v.s;
        dp[v.f].n0 -= dp[v.f].m0 * v.s;

        dp[u].m0 += dp[v.f].m0;
        dp[u].n0 += dp[v.f].n0;
        if( dp[u].s.size() < dp[v.f].s.size() ){
            swap( dp[u].s , dp[v.f].s );
            swap( dp[u].offset , dp[v.f].offset );
        }
        for( auto i : dp[v.f].s )
            dp[u].s.insert(i+dp[v.f].offset-dp[u].offset);
    }

    //cout << u << ' ' << getmin(u) << '\n';

    while( dp[u].m0 + dp[u].s.size() > 1 ){
        auto it = dp[u].s.end(); it--;
        dp[u].s.erase(it);
    }

    stack<ll> l2;
    for(int i=0; i<2; i++){
        auto it = dp[u].s.end(); it--;
        l2.push(*it+dp[u].offset);
        dp[u].s.erase(it);
    }

    dp[u].offset -= pedge[u];//db(u)db(pedge[u])
    dp[u].n0 += ( dp[u].m0 + 1 ) * ( pedge[u] );
    //dp[u].n0 = pedge[u];

    while( !l2.empty() ){
        dp[u].s.insert(l2.top()-dp[u].offset);
        l2.pop();
    }

    //cout << u << ' ' << getmin(u) << '\n';//db(pedge[u])
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout.setf(ios::fixed); cout.precision(10);

    //freopen("a.in","r",stdin);
    //freopen("a.in","w",stdout);

    cin >> n >> m;

    for(int i=2; i<=n+m; i++){
        cin >> p[i] >> pedge[i];
        g[p[i]].push_back({i,pedge[i]});
    }

    dfs(1);

    cout << getmin(1) << '\n';

    return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'll getmin(int)':
fireworks.cpp:55:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int i=1; i<v.size(); i++){
      |                  ~^~~~~~~~~

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