Submission #470463

#TimeUsernameProblemLanguageResultExecution timeMemory
470463humbertoyustaFireworks (APIO16_fireworks)C++14
19 / 100
32 ms56808 KiB
#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 (stderr)

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++){
      |                  ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...