제출 #883076

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
883076		nghiaaa	Harbingers (CEOI09_harbingers)	C++14	30 / 100	133 ms	65536 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define ii pair<int,int>
#define f first
#define s second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define all(v) v.begin(),v.end()
#define BIT(i) ((ll)1<<(i))
#define endl "\n"
#define debug(x) for (auto p: x) cout<<p<<' ';cout<<endl
#define forw(i,j,z) for(int i=(int)j;i<=(int)z;i++)
#define forw2(i,j,z,k) for(int i=(int)j;i<=(int)z;i+=k)
#define ford(i,j,z) for (int i=(int)j;i>=(int)z;i--)
#define ford2(i,j,z,k) for (int i=(int)j;i>=(int)z;i-=k)
#define sz(a) (int)a.size()
const ll inf=LLONG_MAX;
const int N=1e5;
struct Line{
    mutable ll a,b; mutable ll pos;
    Line(ll a1,ll b1):a(a1),b(b1),pos(0){}
    bool operator < (const Line &u) const{
        return a<u.a;
    }
    bool operator < (const ll &p) const {
        return pos<p;
    }
};
int timeDFS=0;
vector<pair<bool,Line> > changes[N+1];
struct LineContainer: multiset<Line,less<> >
{
    ll div(ll u,ll v)
    {
        return u/v - ((u^v)<0&&(u%v));
    }
    bool isect(iterator x,iterator y)
    {
        changes[timeDFS].push_back(mp(1,*x));
        if (y==end()){
            x->pos=inf;
            changes[timeDFS].push_back(mp(0,*x));
            return 0;
        }
        if (x->a==y->a) x->pos= x->b > y->b ? inf: -inf;
        else x->pos= div(x->b - y->b,y->a - x->a);
        changes[timeDFS].push_back(mp(0,*x));
        return x->pos>=y->pos;
    }
    void add(Line v)
    {
        iterator z=insert(v),y=z++,x=y;
        changes[timeDFS].push_back(mp(0,v));
        while(isect(y,z)){
            changes[timeDFS].push_back(mp(1,*z));
            z=erase(z);
        }
        while((y=x)!=begin()&&isect(--x,y)){
            changes[timeDFS].push_back(mp(1,*y));
            isect(x,erase(y));
        }
    }
    ll query(ll u)
    {
        Line d=*lower_bound(u);
        return d.a*u + d.b;
    }
} haha;
int n;
vector<ii> adj[N+1];
int dp[N+1],h[N+1];
int prepare[N+1],velocity[N+1];
void dfs(int u,int dad)
{
    int now=++timeDFS;
    if (u>1){
        dp[u]=-haha.query(-velocity[u])+h[u]*velocity[u]+prepare[u];
        haha.add(Line(-h[u],-(dp[u])));
    }
    forw(i,0,sz(adj[u])-1) if (adj[u][i].f!=dad)
    {
        int v=adj[u][i].f,d=adj[u][i].s;
        h[v]=h[u]+d;
        dfs(v,u);
    }
    if (u>1){
        ford(i,sz(changes[now])-1,0)
        {
            if (changes[now][i].f==0)
                haha.erase(haha.find(changes[now][i].s));
            else haha.insert(changes[now][i].s);
        }
        changes[now].clear();
    }
}
void solve()
{
    haha.add(Line(0,0));
    cin>>n;
    forw(i,2,n)
    {
        int u,v,d;
        cin>>u>>v>>d;
        adj[u].push_back(mp(v,d));
        adj[v].push_back(mp(u,d));
    }
    forw(i,2,n) cin>>prepare[i]>>velocity[i];
    dfs(1,1);
    forw(i,2,n) cout<<dp[i]<<' ';
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //cout<<setprecision(6)<<fixed;
    //time_t TIME_TU=clock();
    int t=1;
    //cin>>t;
    while(t--)
        solve();
    //time_t TIME_TV=clock();
    //cerr<<(db)(TIME_TV-TIME_TU)/CLOCKS_PER_SEC<<endl;
    return 0;
}

• Subtask 1: 30 / 100