Submission #1246719

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246719		escobrand	Harbingers (CEOI09_harbingers)	C++20	100 / 100	77 ms	29252 KiB

harbingers

#include <bits/stdc++.h>

using namespace std;
#define se second
#define fi first
#define ll long long
#define all(a) a.begin(),a.end()
#define eb push_back
#define ld long double
typedef pair<int,int> pii;
int i,n,t,u,v,w;
const int maxn = 1e5 + 10;
vector<pii> adj[maxn];
ll d[maxn],a[maxn],b[maxn],dp[maxn];

struct line
{
  ll a,b;
  line():a(0),b(0){};
  line(ll A,ll B):a(A),b(B){};

  ll cal(const ll &x){return a * x + b;}
  friend ld xcut(const line &a,const line &b){return (ld)(b.b - a.b) / (a.a - b.a);}
  friend bool check(const line &a,const line &b,const line &c){return xcut(a,b)<xcut(b,c);}
};

struct cht
{
  line hull[maxn * 2];
  struct mem
  {
    int pos,S;
    line value;
  };
  stack<mem>st;
  int sz = 0;

  void push(const line & a)
  {
    int l = 1,r = sz,mid;
    while(l < r)
    {
      mid = (l + r)/2;
      if(!check(hull[mid-1],hull[mid],a))
      {
        r = mid;
      }
      else l = mid + 1;
    }
    l = r;
    st.push({l,sz,hull[l]});
    hull[l] = a;
    sz = l + 1;
  }

  void fix()
  {
    if(st.empty())return;
    mem tmp = st.top();
    st.pop();
    hull[tmp.pos] = tmp.value;
    sz = tmp.S;
  }

  ll cal(const ll &x)
  {
    int l = 0,r = sz-1,mid;
    while(l<r)
    {
      mid = (l + r)/2;
      if(xcut(hull[mid],hull[mid+1]) < x)l = mid+1;
      else r = mid;
    }
    return hull[l].cal(x);
  }
}lc;

void dfs(int i,int p)
{
  // if(i == 6 || i == 8)
  // {
  //   for(int k = 0;k<lc.sz;k++)cout<<lc.hull[k].a<<' '<<lc.hull[k].b<<'\n';
  //   cout<<d[i]<<'\n';
  // }
  if(i > 1)
  {
    dp[i] = a[i] * d[i] + b[i];
    if(p != 1)
    {
      dp[i] = min(dp[i],lc.cal(a[i]) + a[i] * d[i] + b[i]);
    }
    lc.push(line(-d[i],dp[i]));
  }
  for(pii k : adj[i])
  {
    if(k.fi == p)continue;
    d[k.fi] = d[i] + k.se;
    dfs(k.fi,i);
  }
  if(i > 1)lc.fix();
}
// dp[j] - d[j] * a[i] + a[i] * d[i] b[i]


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(i = 1;i<n;i++)
    {
      cin>>u>>v>>w;
      adj[u].eb({v,w});
      adj[v].eb({u,w});
    }
    for(i = 2;i<=n;i++)cin>> b[i]>>a[i];
    dfs(1,0);
    for(i = 2;i<=n;i++)cout<<dp[i]<<' ';

    return 0;
}

• Subtask 1: 100 / 100