Submission #856618

#	Time	Username	Problem	Language	Result	Execution time	Memory
856618		efedmrlr	Harbingers (CEOI09_harbingers)	C++17	20 / 100	120 ms	65536 KiB

harbingers

#include <bits/stdc++.h>

using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int (i) = 0; (i) < (n); (i)++)

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const long double EPS = 0.000001;
const lli INF = 1e18+50;
const int N = 1e5+5;
const int ALPH = 26;
const int LGN = 25;
const int MOD = 1e9+7;
const int MAXR = 1e9+5;
int n;

struct Line {
    int m,c;
    Line() {
        m = 1e9+5;
        c = 1e9+5;
    }
    Line(int a, int b) {
        m = a; 
        c = b;
    }
    lli eval(int x) {
        return (lli) m*x + c;
    }
};

struct Node {
    Node *lc, *rc;
    Line data;
    Node() {
        lc = NULL;
        rc = NULL;
        data = Line();
    }
    Node(Line val) {
        data = val;
        lc = NULL;
        rc = NULL;
    }
    void push() {
        if(lc == NULL) lc = new Node();
        if(rc == NULL) rc = new Node();
    }
    lli query(int tl, int tr, int ind) {
        if(tl == tr) {
            return data.eval(ind);
        }
        push();
        int tm = (tl + tr) / 2;
        if(ind <= tm) {
            return min( data.eval(ind), lc->query(tl, tm, ind) );
        }
        else {
            return min( data.eval(ind), rc->query(tm+1, tr, ind) );
        }
    }
};
Node *update(Node *v, int tl, int tr, Line nw) {
    if(tl == tr) {
        if(v->data.eval(tl) > nw.eval(tl)) {
            return new Node(nw);
        }
        else {
            return new Node(*v);
        }
    }
    v->push();
    int tm = (tl + tr) / 2;
    Node *ret = new Node(*v);
    if(ret->data.m > nw.m) {
        swap(ret->data , nw);
    }
    if(ret->data.eval(tm) > nw.eval(tm)) {
        swap(nw, ret->data);
        ret->rc = update(v->rc, tm+1, tr, nw);
    }
    else {
        ret->lc = update(v->lc, tl, tm, nw);
    }
    return ret;
}
int harv[N], hars[N], path[N];
Node *roots[N];
vector<array<int,2> > adj[N];
lli res[N];
void dfs(int node, int par) {
    res[node] = harv[node] * path[node] + hars[node] + roots[par]->query(0, MAXR, harv[node]);
    roots[node] = update(roots[par] , 0, MAXR, Line(-path[node], res[node]));
    for(auto c : adj[node]) {
        if(c[0] == par) continue;
        path[c[0]] = c[1] + path[node];
        dfs(c[0], node);

    }
    
}

inline void solve() {
    cin>>n;
    for(int i = 0; i<n-1; i++) {
        int u, v, d;
        cin>>u>>v>>d;
        adj[u].pb({v, d});
        adj[v].pb({u, d});
    }
    for(int i = 2; i<=n; i++) {
        cin>>hars[i]>>harv[i];
    }
    path[1] = 0;
    roots[0] = new Node();
    roots[0] = update(roots[0], 0, MAXR, Line(0, 0));
    dfs(1, 0);
    for(int i = 2; i<=n; i++) {
        cout<<res[i]<<"\n";
    }
}
 
signed main() {

    fastio();
    int test = 1;
    //cin>>test;
    while(test--) {
        solve();
    }
    
}

• Subtask 1: 20 / 100