Submission #934017

#	Time	Username	Problem	Language	Result	Execution time	Memory
934017		mraron	Harbingers (CEOI09_harbingers)	C++14	100 / 100	91 ms	28804 KiB

harbingers

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<unordered_map>
#include<unordered_set>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<numeric>
#include<random>
#include<chrono>
#include<bitset>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define sz(x) (int)(x).size()
#define gc getchar
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mp make_pair
#define ins insert
#define chkmn(x,y) (x)=min((x), (y))
#define chkmx(x,y) (x)=max((x), (y))

#ifndef ONLINE_JUDGE
#  define LOG(x) (cerr << #x << " = " << (x) << endl)
#else
#  define LOG(x) ((void)0)
#endif

using ll = long long;
using ull = unsigned long long ;
using ld = long double ;
using str = string;
//using ordered_set=tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update>;

const double PI=acos(-1);
const ll INF = 1LL<<62;
const ll MINF = -(1LL<<62);

template<typename T> T getint() {
    T val=0;
    char c;
    
    bool neg=false;
    while((c=gc()) && !(c>='0' && c<='9')) {
        neg|=c=='-';
    }

    do {
        val=(val*10)+c-'0';
    } while((c=gc()) && (c>='0' && c<='9'));

    return val*(neg?-1:1);
}

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution<int>(0, n-1)(rng)


struct line {
    ll m,b;
    ll at(ll x) const {
        return m*x+b;
    }
};

struct magic_stack {
    int sz=0;
    vector<line> lst;
    
    magic_stack() {
        lst.resize(100501);
    }
    
    bool inter(line x, line y, line z) {
        if(x.m==y.m && x.b>=y.b) return true;
        if(z.m==y.m && z.b>=y.b) return true;
        return ld(x.b-y.b)/(-x.m+y.m)>=ld(y.b-z.b)/(-y.m+z.m);
    }
    
    pair<int, line> add(line l) {
        if(sz<=1) {
            int prev_sz=sz;
            auto tmp=lst[sz];
            lst[sz++]=l;
            return {prev_sz, tmp};
        } 
        int x=sz-1;
        for(int j=20;j>=0;j--) {
            int xx=x-(1<<j);
            if(xx>=0 && inter(lst[xx],lst[xx+1],l)) {
                x=xx;
            }
        }
        x--;
        //~ int y=sz-2;
        //~ while(y>=0 && inter(lst[y],lst[y+1],l)) {
            //~ y--;
        //~ }   
        //~ if(x!=y) {
        //~ for(int i=0;i<sz;++i) cerr<<lst[i].m<<"x + "<<lst[i].b<<"\n";
        //~ for(int j=0;j+1<sz;++j) cerr<<inter(lst[j],lst[j+1],l)<<" ";cerr<<"\n";
        //~ LOG(x);
        //~ LOG(y);
        //~ assert(x==y);
        //~ }
        
        int prev_sz=sz;
        auto tmp=lst[x+2];
        lst[x+2]=l;
        sz=x+3;
        return {prev_sz, tmp};
    }
    
    ll get(ll x) {
        int L=0, R=sz-1;
        while(L<R) {
            int mid=(L+R)/2;
            if(lst[mid].at(x)<lst[mid+1].at(x)) {
                R=mid;
            }else {
                L=mid+1;
            }
        }
        return lst[L].at(x);
    }
    
    
    
    void debug() {
        for(auto i:lst) cerr<<i.m<<" "<<i.b<<"\n";
    }
};

vector<pair<int,ll>> adj[100001];
ll s[100001], v[100001], ans[100001];
int st[100010];
pair<int, line> todo[100010];
void dfs(int x, magic_stack& ms, ll depth=0) {
    st[x]=1;
    if(x>1) {
        ans[x]=depth*v[x]+s[x];
        if(ms.lst.size()>0) {
            ans[x]=min(ans[x], ms.get(v[x])+s[x]+depth*v[x]);
        }
        todo[x]=ms.add(line{-depth, ans[x]});
    }

    for(auto i:adj[x]) {
        if(!st[i.xx]) {
            dfs(i.xx, ms, depth+i.yy);
        }
    }
    
    if(x>1) {
        ms.lst[ms.sz-1]=todo[x].yy;
        ms.sz=todo[x].xx;
    }
}

int main() {
    IO;
    //bazd meg ojuz
    //freopen("harbingers.in", "r", stdin);
    //freopen("harbingers.out", "w", stdout);
    int n;
    cin>>n;
    for(int i=0;i<n-1;++i) {
        int a,b,c;
        cin>>a>>b>>c;
        adj[a].pb({b,c});
        adj[b].pb({a,c});
    }
    for(int i=2;i<=n;++i) {
        cin>>s[i]>>v[i];
    }
    
    magic_stack ms;
    dfs(1, ms);
    for(int i=2;i<=n;++i) cout<<ans[i]<<" \n"[i==n];
    
    return 0;
}

• Subtask 1: 100 / 100