Submission #1001172

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001172		vjudge1	Fireworks (APIO16_fireworks)	C++17	0 / 100	1 ms	604 KiB

fireworks

#include <bits/stdc++.h>
 
#define ll long long
#define lb lower_bound
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F first
#define S second
#define ld long double
#define pb push_back
#define all(v) v.begin(),v.end()
#define in insert
#define sz(s) (int)s.size()
#define int ll
#define ppb pop_back

using namespace std;
 
const int MAX=1000+10;
const int inf=2e9;

int n,m;
vector<int> g[MAX];
int a[MAX];

struct DP{
  multiset<int> l,r;
  int add,slope,st;

  DP(){
    st=0;
    add=0;
    slope=0;
  }
}dp[MAX];

void mrg(int v,int to){
  if(sz(dp[v].l)<sz(dp[to].l)){
    swap(dp[v],dp[to]);
  }
  dp[v].slope+=dp[to].slope;
  dp[v].st+=dp[to].st;
  for(int x:dp[to].l){
    dp[v].l.in(x);
  }
  for(int x:dp[to].r){
    dp[v].r.in(x+dp[to].add-dp[v].add); 
  }
  while(*dp[v].l.rbegin()>*dp[v].r.begin()+dp[v].add){
    int L=*dp[v].l.rbegin()-dp[v].add;
    int R=*dp[v].r.begin()+dp[v].add;
    dp[v].l.erase(--dp[v].l.end());
    dp[v].r.erase(dp[v].r.begin());
    dp[v].l.in(R);
    dp[v].r.in(L);
  }
  while(sz(dp[v].l)>abs(dp[v].slope)){
    dp[v].r.in(*dp[v].l.rbegin()-dp[v].add);
    dp[v].l.erase(--dp[v].l.end());
  }
  while(sz(dp[v].l)<abs(dp[v].slope)){
    dp[v].l.in(*dp[v].r.begin()+dp[v].add);
    dp[v].r.erase(dp[v].r.begin());
  }
  while(sz(dp[v].r)>1){
    dp[v].r.erase(--dp[v].r.end());
  }
}

void dfs(int v){
  if(sz(g[v])==0){
    dp[v].slope=-1;
    dp[v].st=a[v];
    dp[v].l.in(a[v]);
    dp[v].r.in(a[v]);
    return;
  }
  for(auto to:g[v]){
    dfs(to);
    mrg(v,to);
  }
  int L=*dp[v].l.rbegin();
  dp[v].st+=a[v];
  dp[v].l.erase(--dp[v].l.end());
  dp[v].add+=a[v];
  dp[v].l.in(L+a[v]);
  dp[v].l.in(L+a[v]);
}

void solve(){
  cin>>n>>m;
  for(int i=2;i<=n+m;i++){
    int p;
    cin>>p>>a[i];
    g[p].pb(i);
  }
  dfs(1);
  int prev=0;
  int ans=dp[1].st;
  // cout<<dp[1].slope<<"\n";
  for(int L:dp[1].l){
    // cout<<L<<" ";
    ans+=(L-prev)*dp[1].slope;
    dp[1].slope++;
    prev=L;
  }
  // cout<<"\n";
  // for(int R:dp[1].r){
  //   cout<<R+dp[1].add<<" ";
  // }
  // cout<<"\n";
  // ans+=*dp[1].r.rbegin()+dp[1].add-prev;
  cout<<ans;
}

// #ifdef LOCAL
signed main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t=1;
  // cin>>t;
  while(t--)solve();
}
// #endif

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