oj.uz

Submission #470464

# Submission time Handle Problem Language Result Execution time Memory
470464 2021-09-04T00:00:02 Z humbertoyusta Fireworks (APIO16_fireworks) C++14
26 / 100
 34 ms 56740 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];

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 + ( (ll)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 '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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 56652 KB Output is correct
2 Correct 29 ms 56652 KB Output is correct
3 Correct 31 ms 56692 KB Output is correct
4 Correct 29 ms 56688 KB Output is correct
5 Correct 29 ms 56612 KB Output is correct
6 Correct 34 ms 56644 KB Output is correct
7 Correct 29 ms 56608 KB Output is correct
8 Correct 29 ms 56600 KB Output is correct
9 Correct 30 ms 56652 KB Output is correct
10 Correct 32 ms 56652 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 56652 KB Output is correct
2 Correct 30 ms 56672 KB Output is correct
3 Correct 28 ms 56740 KB Output is correct
4 Correct 30 ms 56640 KB Output is correct
5 Correct 29 ms 56580 KB Output is correct
6 Correct 32 ms 56704 KB Output is correct
7 Correct 29 ms 56652 KB Output is correct
8 Correct 30 ms 56704 KB Output is correct
9 Correct 29 ms 56620 KB Output is correct
10 Correct 30 ms 56584 KB Output is correct
11 Correct 30 ms 56692 KB Output is correct
12 Correct 31 ms 56644 KB Output is correct
13 Correct 33 ms 56708 KB Output is correct
14 Correct 29 ms 56632 KB Output is correct
15 Correct 33 ms 56688 KB Output is correct
16 Correct 30 ms 56688 KB Output is correct
17 Correct 29 ms 56652 KB Output is correct
18 Correct 29 ms 56704 KB Output is correct
19 Correct 29 ms 56652 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 56652 KB Output is correct
2 Correct 29 ms 56652 KB Output is correct
3 Correct 31 ms 56692 KB Output is correct
4 Correct 29 ms 56688 KB Output is correct
5 Correct 29 ms 56612 KB Output is correct
6 Correct 34 ms 56644 KB Output is correct
7 Correct 29 ms 56608 KB Output is correct
8 Correct 29 ms 56600 KB Output is correct
9 Correct 30 ms 56652 KB Output is correct
10 Correct 32 ms 56652 KB Output is correct
11 Correct 29 ms 56652 KB Output is correct
12 Correct 30 ms 56672 KB Output is correct
13 Correct 28 ms 56740 KB Output is correct
14 Correct 30 ms 56640 KB Output is correct
15 Correct 29 ms 56580 KB Output is correct
16 Correct 32 ms 56704 KB Output is correct
17 Correct 29 ms 56652 KB Output is correct
18 Correct 30 ms 56704 KB Output is correct
19 Correct 29 ms 56620 KB Output is correct
20 Correct 30 ms 56584 KB Output is correct
21 Correct 30 ms 56692 KB Output is correct
22 Correct 31 ms 56644 KB Output is correct
23 Correct 33 ms 56708 KB Output is correct
24 Correct 29 ms 56632 KB Output is correct
25 Correct 33 ms 56688 KB Output is correct
26 Correct 30 ms 56688 KB Output is correct
27 Correct 29 ms 56652 KB Output is correct
28 Correct 29 ms 56704 KB Output is correct
29 Correct 29 ms 56652 KB Output is correct
30 Incorrect 30 ms 56716 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 56652 KB Output is correct
2 Correct 29 ms 56652 KB Output is correct
3 Correct 31 ms 56692 KB Output is correct
4 Correct 29 ms 56688 KB Output is correct
5 Correct 29 ms 56612 KB Output is correct
6 Correct 34 ms 56644 KB Output is correct
7 Correct 29 ms 56608 KB Output is correct
8 Correct 29 ms 56600 KB Output is correct
9 Correct 30 ms 56652 KB Output is correct
10 Correct 32 ms 56652 KB Output is correct
11 Correct 29 ms 56652 KB Output is correct
12 Correct 30 ms 56672 KB Output is correct
13 Correct 28 ms 56740 KB Output is correct
14 Correct 30 ms 56640 KB Output is correct
15 Correct 29 ms 56580 KB Output is correct
16 Correct 32 ms 56704 KB Output is correct
17 Correct 29 ms 56652 KB Output is correct
18 Correct 30 ms 56704 KB Output is correct
19 Correct 29 ms 56620 KB Output is correct
20 Correct 30 ms 56584 KB Output is correct
21 Correct 30 ms 56692 KB Output is correct
22 Correct 31 ms 56644 KB Output is correct
23 Correct 33 ms 56708 KB Output is correct
24 Correct 29 ms 56632 KB Output is correct
25 Correct 33 ms 56688 KB Output is correct
26 Correct 30 ms 56688 KB Output is correct
27 Correct 29 ms 56652 KB Output is correct
28 Correct 29 ms 56704 KB Output is correct
29 Correct 29 ms 56652 KB Output is correct
30 Incorrect 30 ms 56716 KB Output isn't correct
31 Halted 0 ms 0 KB -