제출 #1167175

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167175		spycoderyt	Harbingers (CEOI09_harbingers)	C++20	0 / 100	88 ms	24644 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;

int inter(Line x,Line y) {
    return (x.b - y.b) / (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;
        }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() {
    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: 0 / 100