Submission #850205

#	Time	Username	Problem	Language	Result	Execution time	Memory
850205		vjudge1	Harbingers (CEOI09_harbingers)	C++17	100 / 100	115 ms	17716 KiB

harbingers

#include <cstdio>
#include <stack>
#include <vector>
using namespace std;
using lf=long double;
constexpr int N=1e5+5;
int n,eh[N],ec;
struct{int nxt,to,dis;}e[N<<1];
int s[N],v[N];
long long dep[N],f[N];
void adde(int u,int v,int w){
    e[++ec]={eh[u],v,w},eh[u]=ec;
}
long long X(int u){return dep[u];}
long long Y(int u){return f[u];}
lf slope(int a,int b){
    return 1.0l*(Y(a)-Y(b))/(1.0*(X(a)-X(b)));
}
bool del(int a,int b,int c){
    // 判断 b 前后分别是 a 和 b 时 b 是否被删除
    return slope(a,b)>=slope(b,c);
}
bool cmp(long long kk,int a,int b){
    // a 是否不劣于 b
    return slope(a,b)>=kk;
}
struct UndoStack{
    struct Info{
        // 记录对 q 数组的一次(真实的)修改操作用于撤销
        int p,ot,ov;
        Info(int p,int ot,int ov):p{p},ot{ot},ov{ov}{};
    };
    int top;
    int q[N];
    stack<Info> rec;
    void push(int v){
        int l{1},r{top};
        while(l<r){
            int mid{(l+r)>>1};
            if(mid==top||del(q[mid],q[mid+1],v)) r=mid;
            else l=mid+1;
        }
        int res{l};
        ++res;
        rec.emplace(res,top,q[res]);
        q[top=res]=v;
    }
    void undo(){
        auto t=rec.top();rec.pop();
        top=t.ot,q[t.p]=t.ov;
    }
    int query(long long kk)const{
        int l{1},r{top};
        while(l<r){
            int mid((l+r)>>1);
            if(mid==top||cmp(kk,q[mid],q[mid+1])) r=mid;
            else l=mid+1;
        }
        return q[l];
    }
}qq;
void dfs(int u,int fa){
    if(u==1) f[u]=0;
    else{
        int x=qq.query(v[u]);
        f[u]=1ll*v[u]*(dep[u]-dep[x])+s[u]+f[x];
    }
    qq.push(u);
    for(int i(eh[u]);i;i=e[i].nxt){
        int v{e[i].to},w{e[i].dis};
        if(v==fa) continue;
        dep[v]=dep[u]+w;
        dfs(v,u);
    }
    qq.undo();
}
signed main(){
    scanf("%d",&n);
    for(int i{1};i<n;++i){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        adde(u,v,w),adde(v,u,w);
    }
    for(int i{2};i<=n;++i){
        scanf("%d%d",s+i,v+i);
    }
    dfs(1,0);
    for(int i(2);i<=n;++i)
        printf("%lld%c",f[i]," \n"[i==n]);
    return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'int main()':
harbingers.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
harbingers.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         scanf("%d%d%d",&u,&v,&w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
harbingers.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         scanf("%d%d",s+i,v+i);
      |         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100