Submission #1167180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167180		spycoderyt	Harbingers (CEOI09_harbingers)	C++20	100 / 100	101 ms	24648 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int N = 3e5+5;
struct Line{
    int a,b;
    int operator()(int x) {return a * x + b;};
}lines[N];
vector<pair<int,int> > A[N];
int dis[N],prep[N],v[N],dp[N];
int sz=1;

long double inter(Line x,Line y) {
    return (long double)(x.b - y.b) / (long double)(y.a - x.a);
}
stack<tuple<int,int,Line> > his;
void add(Line nw) {
    int pos = sz, l = 1, r = sz-1;
    while(l<=r){
        int mid = (l+r)/2;
        if(inter(lines[mid-1],nw) >= inter(lines[mid],nw)){
            pos=mid;
            r=mid-1;   
        }else l=mid+1;
    }
    his.emplace(sz,pos,lines[pos]);
    lines[pos]=nw;
    sz=pos+1;
}
int query(int x) {
    int pos = 0, l = 1, r = sz-1;
    while(l<=r){
        int mid=(l+r)/2;
        if (lines[mid - 1](x) >= lines[mid](x)){
            pos=mid;
            l=mid+1;
        }else r=mid-1;
    }
    return lines[pos](x);
}
void rollback() {
    auto [a,b,c] = his.top();
    his.pop();
    lines[b]=c;
    sz=a;
}
void dfs(int u,int par = -1) {
    if(par!=-1){
        dp[u] = prep[u] + v[u] * dis[u] + query(v[u]);
        add({-dis[u],dp[u]});
    }
    for(auto [nxt,w] : A[u])if(nxt!=par){
        dis[nxt] = dis[u] + w;
        dfs(nxt,u);
    }
    if(par!=-1)rollback();
}
int32_t main() {

//   if (fopen("read.inp", "r")){
//     freopen("read.inp", "r", stdin);
//     freopen("write.out", "w", stdout);
//   }
    cin.tie(0)->sync_with_stdio(0);
    int a,b,w,n;
    cin >> n;
    for(int i = 0;i<n-1;i++) {
        cin >> a >> b >> w;
        A[a].push_back({b,w});
        A[b].push_back({a,w});
    }
    for(int i = 2;i<=n;i++)cin>>prep[i]>>v[i];
    // get dis values + do lichao
    dfs(1);
    for(int i = 2;i<=n;i++) cout << dp[i] << " ";
}

• Subtask 1: 100 / 100