oj.uz

Submission #474848

# Submission time Handle Problem Language Result Execution time Memory
474848 2021-09-20T04:57:51 Z aniervs Harbingers (CEOI09_harbingers) C++17
20 / 100
 170 ms 65540 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = (int)2e5 + 5;

struct PersistentLiChaoTree{

    struct line{
        ll m, b;
        line(){ m = b = 1e9;}
        line(ll _m, ll _b){ m = _m, b = _b; }
        ll eval(ll x){ return m * x + b; }
    };

    struct node{
        node * l,  * r;
        line L;

        node(){ l = 0, r = 0, L = line(); }

        node(node * _l, node * _r, line _L){
            l = _l, r = _r, L = _L;
        }

    };

    node * add_line(node * u, int l, int r, line L){
        
        node * v;
        
        if(u)
            v = new node(u->l, u->r, u->L);
        else
            v = new node(0, 0, L);


        int m = (l + r)>>1;
        bool lef = L.eval(l) < v->L.eval(l);
        bool mid = L.eval(m) < v->L.eval(m);

        if(mid)
            swap(v->L, L);
        
        if(r - l == 1)
            return v;
        if(lef != mid) {
            v->l = add_line(v->l, l, m, L);
        }
        else{
            v->r = add_line(v->r, m, r, L);
        }
        return v;
    }

    ll get(node * u, int l, int r, int x) {
        int m = (l + r) / 2;
        if(r - l == 1) 
            return u->L.eval(x);
        if(x < m){
            ll q2 = (u->l) ? get(u->l, l, m, x) : LLONG_MAX;
            return min(q2, u->L.eval(x));
        }   
        ll q2 = (u->r) ? get(u->r, m, r, x) : LLONG_MAX;

        return min(q2, u->L.eval(x));
    }

    vector<node*> roots;

    PersistentLiChaoTree(){
        node * u = new node(0, 0, line());
        roots.push_back(u);
    }

    int update(int old, line l){
        roots.push_back(add_line(roots[old], 0, 1e9, l));
        return (int)roots.size() - 1;
    }
    ll query(int id, ll x){
        return get(roots[id], 0, 1e9, x);
    }

} lt;

vector<pair<int,int>> G[maxn];
ll speed[maxn], start[maxn], dp[maxn], sumW[maxn];
int n, par[maxn];
int pos[maxn];

void dfs(int u){
    pos[u] = lt.update(pos[par[u]], PersistentLiChaoTree::line(-sumW[u], dp[u]));

    for(auto [v, w]:G[u]){
        if(v == par[u])
            continue;
        
        sumW[v] = sumW[u] + w; 
        par[v] = u;

        dp[v] = sumW[v] * speed[v] + start[v] + lt.query(pos[u], speed[v]);

        dfs(v);
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n;
    for(int i = 1; i < n; i++){
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }  

    for(int i = 2; i <= n; i++)
        cin >> start[i] >> speed[i];

    dfs(1);

    for(int i = 2; i <= n; i++)
        cout << dp[i] << ' ';   
    
    cout << endl;
    
    return 0;
}

Subtask #1
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5196 KB Output is correct
2 Correct 10 ms 9164 KB Output is correct
3 Runtime error 108 ms 65540 KB Execution killed with signal 9
4 Runtime error 121 ms 65540 KB Execution killed with signal 9
5 Runtime error 137 ms 65540 KB Execution killed with signal 9
6 Runtime error 144 ms 65540 KB Execution killed with signal 9
7 Runtime error 131 ms 65540 KB Execution killed with signal 9
8 Runtime error 170 ms 65540 KB Execution killed with signal 9
9 Runtime error 150 ms 65540 KB Execution killed with signal 9
10 Runtime error 142 ms 65540 KB Execution killed with signal 9