Submission #602340

#	Time	Username	Problem	Language	Result	Execution time	Memory
602340		Bench0310	Harbingers (CEOI09_harbingers)	C++17	100 / 100	140 ms	23992 KiB

harbingers

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

struct line
{
    ll k,n;
    line(){}
    line(ll a,ll b){k=a;n=b;}
    ll eval(ll x){return (k*x+n);}
    friend double intersect(line &a,line &b){return (double(b.n-a.n)/(a.k-b.k));}
    friend bool ok(line &a,line &b,line &c){return (intersect(a,b)<intersect(b,c));}
};

const int N=100005;
int n;
array<int,3> v[2*N];
int vstart[N];
int ts[N];
int tv[N];
int depth[N];
line trie[N];
int ver[N]; //version of node i
double lim[N];
int p[N][17];
int tcnt=1;
ll res[N];

int add(int a,line l)
{
    int to=(++tcnt);
    for(int j=16;j>=0;j--)
    {
        int y=p[a][j];
        int x=p[y][0];
        if(x!=0&&y!=0&&!ok(trie[x],trie[y],l)) a=y;
    }
    if(a!=0&&p[a][0]!=0&&!ok(trie[p[a][0]],trie[a],l)) a=p[a][0];
    trie[to]=l;
    p[to][0]=a;
    for(int j=1;j<17;j++) p[to][j]=p[p[to][j-1]][j-1];
    lim[to]=intersect(trie[a],trie[to]);
    return to;
}

ll opt(int a,ll x)
{
    for(int j=16;j>=0;j--)
    {
        int u=p[a][j];
        if(u!=0&&lim[u]>x) a=u;
    }
    if(lim[a]>x) a=p[a][0];
    return trie[a].eval(x);
}

void dfs(int a,int u)
{
    if(a==1)
    {
        ver[a]=1;
        trie[1]=line(0,0);
        lim[1]=-1e100;
    }
    else
    {
        res[a]=ts[a]+opt(ver[u],tv[a])+ll(depth[a])*tv[a];
        ver[a]=add(ver[u],line(-depth[a],res[a]));
    }
    for(int i=vstart[a];i<2*(n-1)&&v[i][0]==a;i++)
    {
        int b=v[i][1];
        int c=v[i][2];
        if(b==u) continue;
        depth[b]=depth[a]+c;
        dfs(b,a);
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i=0;i<n-1;i++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        v[2*i]={a,b,c};
        v[2*i+1]={b,a,c};
    }
    sort(v,v+2*(n-1));
    for(int i=2*(n-1)-1;i>=0;i--) vstart[v[i][0]]=i;
    for(int i=2;i<=n;i++) cin >> ts[i] >> tv[i];
    dfs(1,0);
    for(int i=2;i<=n;i++) cout << res[i] << " \n"[i==n];
    return 0;
}

• Subtask 1: 100 / 100