Submission #1117652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117652		vjudge1	Harbingers (CEOI09_harbingers)	C++17	20 / 100	165 ms	65536 KiB

harbingers

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define II signed
struct {
    struct line{
        II K;
        int B;
        line(int k,int b){
            K=k,B=b;
        }
        line(){
            K=0;
            B=1e18;
        }
        inline int operator()(int x){
            return K*x+B;
        }
    } T[100100];
    II lc[100100],rc[100100],rt,CCC;
    stack<pair<II,line>> oppss;
    void update(II &i,int l,int r,line s){
        if(!i)i=++CCC;
        if(T[i].B==1e18) return T[i]=s,oppss.push({i,s});
        if(l==r-1){
            if(s(l)<T[i](l))
                swap(s,T[i]),
                oppss.push({i,s});
            return;
        }
        if(s.K<T[i].K)
            swap(s,T[i]),
            oppss.push({i,s});
        int mid=l+r>>1;
        if(s(mid) < T[i](mid)) swap(s,T[i]),
            oppss.push({i,s}),update(rc[i],mid,r,s);
        else update(lc[i],l,mid,s);
    }
    int query(int i,int l,int r,int p){
        if(!i)return 1e18;
        if(T[i].B==1e18)
            return 1e18;
        if(l==r-1)
            return T[i](p);
        if(p<l+r>>1)
            return min(T[i](p),query(lc[i],l,l+r>>1,p));
        else return min(T[i](p),query(rc[i],l+r>>1,r,p));
    }
    inline int pointintime(){
        return oppss.size();
    }
    void add_line(int k,int b){
        update(rt,-1,1e9+1,line(k,b));
    }
    int calc_best(int pos){
        return query(rt,-1,1e9+1,pos);
    }
    void rewind(int x){
        while(oppss.size()>x){
            auto[a,b]=oppss.top();
            oppss.pop();
            T[a]=b;
        }
    }
} lichao;
II S[100100],V[100100],res[100100];
vector<pair<II,II>>adj[100100];
void dfs(II n,II p,II d){
    int X = lichao.pointintime();
    if(n==1){
        lichao.add_line(0,0);
    } else {
        res[n] = lichao.calc_best(V[n])+S[n]+d*V[n];
        lichao.add_line(-d,res[n]);
    }
    for(auto[i,j]:adj[n])
        if(i-p)dfs(i,n,j+d);
    lichao.rewind(X);
}

II main(){
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin>>n;
    for(int i=1;i<n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    for(int i=2;i<=n;i++)
        cin>>S[i]>>V[i];
    dfs(1,0,0);
    for(int i=2;i<=n;i++)
        cout<<res[i]<<' ';
}

Compilation message (stderr)

harbingers.cpp: In member function 'void<unnamed struct>::update(int&, long long int, long long int, <unnamed struct>::line)':
harbingers.cpp:34:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |         int mid=l+r>>1;
      |                 ~^~
harbingers.cpp: In member function 'long long int<unnamed struct>::query(long long int, long long int, long long int, long long int)':
harbingers.cpp:45:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |         if(p<l+r>>1)
      |              ~^~
harbingers.cpp:46:47: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |             return min(T[i](p),query(lc[i],l,l+r>>1,p));
      |                                              ~^~
harbingers.cpp:47:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |         else return min(T[i](p),query(rc[i],l+r>>1,r,p));
      |                                             ~^~
harbingers.cpp: In member function 'void<unnamed struct>::rewind(long long int)':
harbingers.cpp:59:27: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<int, <unnamed struct>::line> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   59 |         while(oppss.size()>x){
      |               ~~~~~~~~~~~~^~

• Subtask 1: 20 / 100