Submission #875610

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
875610	2023-11-20T07:37:45 Z	hhnguyen	Harbingers (CEOI09_harbingers)	C++14	80 / 100	85 ms	24372 KB

harbingers

#include <bits/stdc++.h>
#define ll long long
#define x first
#define y second
using namespace std;
const int N = 1e5+5;
typedef pair <ll,ll> ii;
vector <ii> g[N];
ll i,j,n,m,k,t,dp[N],s[N],v[N],d[N],top;
struct operation
{
    ll pos,top;
    ii overwrite;
    operation(ll _p,ll _t,ii _o)
    {
        pos=_p;
        top=_t;
        overwrite=_o;
    }
};
vector <operation> undolist;
ii line[N];
ll dt(ll x,ii d)
{
    return (d.x*x+d.y);
}
bool bad(ii a,ii b,ii c)
{
    return ((b.y-a.y)*(c.x-a.x)<=(c.y-a.y)*(b.x-a.x));
}
ll getmin(ll x)
{
    ll l=0,r=top-1,ans=dt(x,line[l]);
    while(l<r)
    {
        ll mid=(l+r)/2;
        ll val1=dt(x,line[mid]);
        ll val2=dt(x,line[mid+1]);
        if(val1>val2){l=mid+1;}
        else {r=mid;}
        ans=min(ans,min(val1,val2));
    }
    return ans;
}
bool insertline(ii newline)
{
    ll l=1,r=top-1,k=top;
    while(l<=r)
    {
        ll mid=(l+r)/2;
        if(bad(line[mid-1],line[mid],newline))
        {
            k=mid;
            r=mid-1;
        }
        else {l=mid+1;}
    }
    undolist.push_back(operation(k,top,line[k]));
    // pos top overwrite
    top=k+1;
    line[k]=newline;
    return 1;
}
void undo()
{
    operation ope=undolist.back();
    undolist.pop_back();
    top=ope.top;
    line[ope.pos]=ope.overwrite;
}
void dfs(ll u,ll par)
{
    if(u>1)
    {
        dp[u]=getmin(v[u])+s[u]+v[u]*d[u];
    }
    insertline({-d[u],dp[u]});
    for(auto x: g[u])
    {
        ll V=x.x;
        ll W=x.y;
        if(V==par){continue;}
        d[V]=d[u]+W;
        dfs(V,u);
    }
    undo();
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(ll i=1;i<n;i++)
    {
        ll U,V,W;
        cin>>U>>V>>W;
        g[U].push_back({V,W});
        g[V].push_back({U,W});
    }
    for(ll i=2;i<=n;i++)
    {
        cin>>s[i]>>v[i];
    }
    dfs(1,0);
    for(ll i=2;i<=n;i++)
    {
        cout<<dp[i]<<" ";
    }
    return 0;
}
/*
5
1 2 20
2 3 12
2 4 1
4 5 3
26 9
1 10
500 2
2 30
*/

Subtask #1

80.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	7260 KB	Output is correct
2	Correct	3 ms	7696 KB	Output is correct
3	Incorrect	31 ms	14540 KB	Output isn't correct
4	Correct	45 ms	17620 KB	Output is correct
5	Correct	61 ms	21676 KB	Output is correct
6	Correct	70 ms	24372 KB	Output is correct
7	Correct	38 ms	15312 KB	Output is correct
8	Incorrect	69 ms	19520 KB	Output isn't correct
9	Correct	85 ms	20796 KB	Output is correct
10	Correct	61 ms	19520 KB	Output is correct