Submission #1167168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167168		spycoderyt	Harbingers (CEOI09_harbingers)	C++20	0 / 100	137 ms	34152 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int N = 3e5+5;
const int inf = 1e17;
int dp[N],st[N],en[N],dis[N],prep[N],v[N];
vector<pair<int,int> > A[N];
int timer = 1;
// lichao with segment and min 
int n;
struct Line{
    int a,b;
    int operator()(int x) {return a * x + b;};
    Line(int x,int y) {
        a=x,b=y;
    }
};
struct Node{
    Line* line;
    Node *left, *right;
    Node(Line* ln) {
        line = ln;
        left=right=nullptr;
    }
    Node() {
        line=nullptr;
        left=right=nullptr;
    }
    void upd(Line* nw,int ll,int rr,int l = 1,int r = n) {
        if(l > rr || r < ll || l > r)return;
        int mid = l + (r-l)/2;
        if(l>=ll&&r<=rr){
            if(!line) {
                line=nw;
                return;
            }
            int ls = (*nw)(l) < (*line)(l);
            int ms = (*nw)(mid) < (*line)(mid);
            if(ms)swap(line,nw);
            if(l==r)return;
            if(ms!=ls){
                if(!left)left = new Node(nw);
                else left->upd(nw,ll,rr,l,mid);
            } else {
                if(!right)right = new Node(nw);
                else right->upd(nw,ll,rr,mid+1,r);
            }
        } else {
            if(!(rr < l || ll > mid)) {
                if(!left) left = new Node();
                left->upd(nw,ll,rr,l,mid);
            }
            if(!(rr < mid + 1 || ll > r)){
                if(!right)right = new Node();
                right->upd(nw,ll,rr,mid+1,r);
            }
        }  
    }
    int qry(int x,int l = 1,int r = n) {
        int res = (line ? (*line)(x) : inf);
        if(l==r)return res;
        int mid = l + (r-l)/2;
        if(x<=mid) {
            if(left)return min(res,left->qry(x,l,mid));
        } if(right) return min(res,right->qry(x,mid+1,r));
        return res;
    }
}t;
void dfs2(int i,int par = -1) {
    if(par!=-1) {
        dp[i] = prep[i] + v[i] * dis[i] + t.qry(v[i]);
        t.upd(new Line(-dis[i],dp[i]),st[i],en[i]);
    }
    for(auto [nxt,w] : A[i])if(nxt!=par)dfs2(nxt,i);
}
void dfs(int u,int par = -1) {
    // do parents
    st[u]=timer++;
    for(auto [nxt,w] : A[u])if(nxt!=par){
        dis[nxt] = dis[u] + w;
        dfs(nxt,u);
    }
    en[u]=timer;
}
int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    int a,b,w;
    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];
    t.upd(new Line(0,0),1,n);
    // get dis values + do lichao
    dfs(1);
    dfs2(1);
    for(int i = 2;i<=n;i++) cout << dp[i] << " ";
}

• Subtask 1: 0 / 100