제출 #1354424

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1354424		Aviansh	Harbingers (CEOI09_harbingers)	C++20	100 / 100	63 ms	26728 KiB

harbingers

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int inf = 3e18;

const int mxn=1e5+5;

int siz=0;

vector<array<int,2>>cht(mxn);

int div2(int a, int b){
    if(b==0){
        return inf;
    }
    return (a/b) - ((a%b)&&((a^b)<0));
}

void dfs(int st, vector<array<int,2>>g[], int dep, int p, long long dp[], int t[], int v[]){
    if(st){
        ///for v[st] find minima
        int lo = 0;
        int hi = siz-1;
        while(lo<hi){
            int mid = (lo+hi)/2;
            int x = div2(cht[mid][1]-cht[mid+1][1],cht[mid+1][0]-cht[mid][0]);
            if(x<v[st]){
                lo=mid+1;
            }
            else{
                hi=mid;
            }
        }
        dp[st]=t[st]+v[st]*dep+(cht[lo][0]*v[st]+cht[lo][1]);
    }
    else{
        dp[st]=0;
        siz++;
    }
    int m = -dep;
    int c = dp[st];
    int lo = 0;
    int hi = siz;
    while(lo<hi){
        int mid = (lo+hi)/2;
        int x = div2(cht[mid][1]-c,m-cht[mid][0]);
        int x2 = -inf;
        if(mid){
            x2=(div2(cht[mid][1]-cht[mid-1][1],cht[mid-1][0]-cht[mid][0]));
        }
        if(x>x2){
            lo=mid+1;
        }
        else{
            hi=mid;
        }
    }
    int osiz = siz;
    int om = cht[lo][0];
    int oc = cht[lo][1];
    siz=lo+1;
    cht[lo][0]=m;
    cht[lo][1]=c;
    for(array<int,2>e:g[st]){
        if(e[0]==p)
            continue;
        dfs(e[0],g,dep+e[1],st,dp,t,v);
    }
    siz=osiz;
    cht[lo][0]=om;
    cht[lo][1]=oc;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<array<int,2>>g[n];
    for(int i = 0;i<n-1;i++){
        int u,v,d;
        cin >> u >> v >> d;
        u--;v--;
        g[u].push_back({v,d});
        g[v].push_back({u,d});
    }
    int t[n];
    int v[n];
    t[0]=0;
    v[0]=0;
    for(int i = 1;i<n;i++){
        cin >> t[i];
        cin >> v[i];
    }
    long long dp[n];
    dfs(0,g,0,-1,dp,t,v);
    for(int i = 1;i<n;i++){
        cout << dp[i] << " ";
    }
    return 0;
}

• 서브태스크 1: 100 / 100