제출 #1354371

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

harbingers

#include <bits/stdc++.h>

using namespace std;

#define int long long

struct line{
    mutable long long m,c,p;
    bool operator<(const line &o) const {return m>o.m;}
    bool operator<(long long x) const {return p<x;}
};

///persistant lineContainer
struct lineContainer : multiset<line,less<>>{
    vector<int>roller;
    vector<array<long long,2>>roll;
    const long long inf = 1e18;
    long long div(long long a, long long b){
        return (a/b)-((a%b)&&((a^b)<0));
    }
    bool isect(iterator x, iterator y){
        if(y==end()){
            x->p=inf;
            return 0;
        }
        if(x->m==y->m){
            x->p = (x->c<=y->c) ? inf : -inf;
        }
        else{
            x->p = div(x->c-y->c,y->m-x->m);
        }
        return x->p>=y->p;
    }
    void add(long long m, long long c, bool r=1){
        auto z = insert({m,c,-inf});
        int cnt = 0;
        auto y = z++;
        auto x = y;
        bool rel=0;
        while(isect(y,z)){
            if(r){
                roll.push_back({z->m,z->c});
                cnt++;
            }
            else{
                assert(0);
            }
            z=erase(z);
        }
        if(x!=begin() && isect(--x,y)){
            if(r){
                roll.push_back({y->m,y->c});
                cnt++;
            }
            else{
                assert(0);
            }
            isect(x,y=erase(y));
        }
        while((y=x)!=begin()&&(--x)->p>=y->p){
            if(r){
                roll.push_back({y->m,y->c});
                cnt++;
            }
            else{
                assert(0);
            }
            isect(x,erase(y));
        }
        if(r){
            roll.push_back({m,c});
            roller.push_back(cnt);
        }
    }
    long long query(long long x){
        line l = *lower_bound(x);
        return l.m*x+l.c;
    }
    void rollback(){
        assert(roller.size());
        array<long long,2>a = roll.back();
        roll.pop_back();
        line l = *lower_bound({a[0],a[1],-inf});
        if(l.m==a[0]&&l.c==a[1]){
            erase(l);
        }
        for(int i = 0;i<roller.back();i++){
            add(roll.back()[0],roll.back()[1],0);
            roll.pop_back();
        }
        roller.pop_back();
    }
};

void dfs(int st, vector<array<int,2>>g[], int dep, int p, long long dp[], int t[], int v[], lineContainer lc){
    if(st){
        dp[st]=t[st]+v[st]*dep+lc.query(v[st]);
    }
    else{
        dp[st]=0;
    }
    lc.add(-dep,dp[st]);
    for(array<int,2>e:g[st]){
        if(e[0]==p)
            continue;
        dfs(e[0],g,dep+e[1],st,dp,t,v,lc);
    }
    //lc.rollback();
}

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];
    lineContainer lc;
    dfs(0,g,0,-1,dp,t,v,lc);
    for(int i = 1;i<n;i++){
        cout << dp[i] << " ";
    }
    return 0;
}

• 서브태스크 1: 10 / 100