Submission #434331

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
434331	2021-06-21T00:52:18 Z	ScarletS	Harbingers (CEOI09_harbingers)	C++17	20 / 100	257 ms	65540 KB

harbingers

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e5+4;
const ll INF = 1e18;
int s[N], v[N];
ll dp[N];
vector<array<int,2>> e[N];

ll f(ll a, ll b, int x)
{
    return a*x+b;
}

struct LiChao
{
    struct node
    {
        ll a = 0, b = 0;
        node *l, *r;
    };
    int n;
    node *root;
    deque<node> buffer;
    stack<deque<node*>> stk1;
    stack<vector<array<ll,2>>> stk2;
    stack<array<ll,2>> lines;
    node *newnode()
    {
        buffer.emplace_back();
        return &buffer.back();
    }
    LiChao(int n) : n(n) {root = newnode();}
    void update(node *&v, int l, int r, ll a, ll b)
    {
        if (!v)
            v=newnode();
        if (f(a,b,l)>=f(v->a,v->b,l)&&f(a,b,r)>=f(v->a,v->b,r))
            return;
        if (f(a,b,l)<f(v->a,v->b,l)&&f(a,b,r)<f(v->a,v->b,r))
        {
            stk1.top().emplace_back(v);
            stk2.top().push_back({v->a,v->b});
            v->a=a;
            v->b=b;
            return;
        }
        int m=l+(r-l)/2;
        update(v->l,l,m,a,b);
        update(v->r,m+1,r,a,b);
    }
    void update(ll a, ll b)
    {
        lines.push({a,b});
        stk1.push({});
        stk2.push({});
        update(root,0,n,a,b);
    }
    ll query(node *v, int l, int r, int x)
    {
        if (x<l||r<x||!v)
            return INF;
        if (l==r)
            return f(v->a,v->b,x);
        int m=l+(r-l)/2;
        return min({f(v->a,v->b,x),query(v->l,l,m,x),query(v->r,m+1,r,x)});
    }
    ll query(int x)
    {
        return query(root,0,n,x);
    }
    void rollback()
    {
        for (int i=0;i<(int)stk2.top().size();++i)
            if ((stk1.top()[i])->a==lines.top()[0]&&(stk1.top()[i])->b==lines.top()[1])
            {
                (stk1.top()[i])->a=stk2.top()[i][0];
                (stk1.top()[i])->b=stk2.top()[i][1];
            }
        stk1.pop();
        stk2.pop();
        lines.pop();
    }
};

LiChao lct(1e9);

void dfs(int c, int p, int h)
{
    dp[c]=1LL*v[c]*h+s[c]+lct.query(v[c]);
    lct.update(-h,dp[c]);
    for (auto i : e[c])
        if (i[0]!=p)
            dfs(i[0],c,h+i[1]);
    lct.rollback();
}
  
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,x,y,z;
    cin>>n;
    for (int i=1;i<n;++i)
    {
        cin>>x>>y>>z;
        e[x].push_back({y,z});
        e[y].push_back({x,z});
    }
    for (int i=2;i<=n;++i)
        cin>>s[i]>>v[i];
    dfs(1,0,0);
    for (int i=2;i<=n;++i)
        cout<<dp[i]<<" ";
    return 0;
}

Subtask #1

20.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2636 KB	Output is correct
2	Correct	10 ms	6216 KB	Output is correct
3	Runtime error	128 ms	51276 KB	Memory limit exceeded
4	Runtime error	153 ms	65540 KB	Execution killed with signal 9
5	Runtime error	151 ms	65540 KB	Execution killed with signal 9
6	Runtime error	165 ms	65540 KB	Execution killed with signal 9
7	Runtime error	257 ms	43820 KB	Memory limit exceeded
8	Runtime error	197 ms	65540 KB	Execution killed with signal 9
9	Runtime error	186 ms	65540 KB	Execution killed with signal 9
10	Runtime error	158 ms	65540 KB	Execution killed with signal 9