Submission #1150820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150820		Hamed_Ghaffari	Fireworks (APIO16_fireworks)	C++20	55 / 100	726 ms	565032 KiB

fireworks

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;	
using pll = pair<ll, ll>;

#define X first
#define Y second
#define SZ(x) int(x.size())	
#define pb push_back
#define mins(a,b) (a=min(a,b))

vector<pll> merge(vector<pll> &f, vector<pll> &g) {
  assert(SZ(f)>=3 && SZ(g)>=3);
  vector<pll> h;
  ll fs=(f[0].Y-f[1].Y)/(f[0].X-f[1].X);
  ll gs=(g[0].Y-g[1].Y)/(g[0].X-g[1].X);
  int i=0, j=0;
  while(i<SZ(f) && j<SZ(g)) {
    if(f[i].X<g[j].X) {
      h.pb(pll(f[i].X, f[i].Y+g[j].Y+(f[i].X-g[j].X)*gs));
      i++;
      if(i==SZ(f)) fs = (f[i-1].Y-f[i-2].Y)/(f[i-1].X-f[i-2].X);
      else fs = (f[i-1].Y-f[i].Y)/(f[i-1].X-f[i].X);
    }
    else if(f[i].X>g[j].X) {
      h.pb(pll(g[j].X, g[j].Y+f[i].Y+(g[j].X-f[i].X)*fs));
      j++;
      if(j==SZ(g)) gs = (g[j-1].Y-g[j-2].Y)/(g[j-1].X-g[j-2].X);
      else gs = (g[j-1].Y-g[j].Y)/(g[j-1].X-g[j].X);
    }
    else {
      h.pb(pll(f[i].X, f[i].Y+g[j].Y));
      i++;
      j++;
      if(i==SZ(f)) fs = (f[i-1].Y-f[i-2].Y)/(f[i-1].X-f[i-2].X);
      else fs = (f[i-1].Y-f[i].Y)/(f[i-1].X-f[i].X);
      if(j==SZ(g)) gs = (g[j-1].Y-g[j-2].Y)/(g[j-1].X-g[j-2].X);
      else gs = (g[j-1].Y-g[j].Y)/(g[j-1].X-g[j].X);
    }
  }
  while(i<SZ(f)) {
    h.pb(pll(f[i].X, f[i].Y+g[j-1].Y+(f[i].X-g[j-1].X)*gs));
    i++;
  }
  while(j<SZ(g)) {
    h.pb(pll(g[j].X, g[j].Y+f[i-1].Y+(g[j].X-f[i-1].X)*fs));
    j++;
  }
  return h;
}

vector<pll> merge(vector<vector<pll>> F) {
  vector<vector<pll>> G;
  while(SZ(F)>1) {
    for(int i=1; i<SZ(F); i+=2) G.pb(merge(F[i-1], F[i]));
    if(SZ(F)&1) G.pb(F.back());
    F = G;
    G.clear();
  }
  return F[0];
}

void add_par(vector<pll> &f, int w) {
  while(f.back().Y>f[SZ(f)-2].Y) f.pop_back();
  vector<pll> stk;
  while(f.back().Y==f[SZ(f)-2].Y) {
    stk.pb(f.back());
    f.pop_back();
  }
  stk.pb(f.back());
  for(auto &i : f) i.Y+=w;
  while(!stk.empty()) {
    f.pb(pll(stk.back().X+w, stk.back().Y));
    stk.pop_back();
  }
  f.pb(pll(f.back().X+1, f.back().Y+1));
}

const int MXN = 3e5+5;

int n, m;
vector<pii> g[MXN];
vector<pll> f[MXN];

void dfs(int v, int pw=-1) {
  if(v>n) {
    f[v] = {{pw-1, 1}, {pw, 0}, {pw+1, 1}};
    return;
  }
  vector<vector<pll>> F;
  for(auto [u, w] : g[v]) {
    dfs(u, w);
    F.pb(f[u]);
  }
  f[v] = merge(F);
  if(pw!=-1) add_par(f[v], pw);
}

int32_t main() {
  cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
  cin >> n >> m;
  for(int i=2,p,c; i<=n+m; i++) {
    cin >> p >> c;
    g[p].pb(pii(i, c));
  }
  dfs(1);
  ll ans = 2e18;
  for(auto [x, y] : f[1])
    mins(ans, y);
  cout << ans << '\n';
  return 0;
}

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