oj.uz

Submission #470463

# Submission time Handle Problem Language Result Execution time Memory
470463 2021-09-03T23:52:49 Z humbertoyusta Fireworks (APIO16_fireworks) C++14
19 / 100
 32 ms 56808 KB 
#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];

int 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<int> 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

fireworks.cpp: In function 'int 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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 56652 KB Output is correct
2 Correct 29 ms 56652 KB Output is correct
3 Incorrect 29 ms 56616 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 56576 KB Output is correct
2 Correct 32 ms 56588 KB Output is correct
3 Correct 30 ms 56652 KB Output is correct
4 Correct 30 ms 56696 KB Output is correct
5 Correct 30 ms 56696 KB Output is correct
6 Correct 29 ms 56616 KB Output is correct
7 Correct 30 ms 56656 KB Output is correct
8 Correct 29 ms 56596 KB Output is correct
9 Correct 30 ms 56688 KB Output is correct
10 Correct 30 ms 56644 KB Output is correct
11 Correct 30 ms 56684 KB Output is correct
12 Correct 30 ms 56680 KB Output is correct
13 Correct 31 ms 56728 KB Output is correct
14 Correct 31 ms 56808 KB Output is correct
15 Correct 30 ms 56652 KB Output is correct
16 Correct 29 ms 56700 KB Output is correct
17 Correct 30 ms 56668 KB Output is correct
18 Correct 30 ms 56684 KB Output is correct
19 Correct 30 ms 56664 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 56652 KB Output is correct
2 Correct 29 ms 56652 KB Output is correct
3 Incorrect 29 ms 56616 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 56652 KB Output is correct
2 Correct 29 ms 56652 KB Output is correct
3 Incorrect 29 ms 56616 KB Output isn't correct
4 Halted 0 ms 0 KB -