Submission #131538

#	Time	Username	Problem	Language	Result	Execution time	Memory
131538		lyc	Harbingers (CEOI09_harbingers)	C++14	40 / 100	1088 ms	47352 KiB

harbingers

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

const int MAXN = 1e5+5;

int N;
vector<ii> al[MAXN];
int S[MAXN], V[MAXN];
int p[MAXN];
int d[MAXN];
ll r[MAXN];

struct Line { int m; ll b; };
const Line END = {(int)-2e9, (ll)-3e18};
struct Hull {
    Line v[MAXN], h[MAXN]; 
    int vi = 0, hi = 0;

    int add(Line l) {
        //cout << "ADD " << l.m << " " << l.b << endl;
        int idx = hi;
        while (vi > 2) {
            if (((ll)l.b-v[vi-1].b)*((ll)v[vi-2].m-v[vi-1].m) <= (((ll)v[vi-1].b-v[vi-2].b)*((ll)v[vi-1].m-l.m)))
                h[hi++] = v[vi-1], --vi;
            else break;
        }
        h[hi++] = END;
        v[vi++] = l;
        return idx;
    }

    ll query(int x) {
        //cout << "QUERY " << SZ(v) << ": ";
        //for (auto l : v) cout << "(" << l.m << "," << l.b << ") ";
        //cout << endl;
        int lo = 0, hi = vi-1;
        while (lo < hi) {
            int mid = (lo+hi)/2;
            bool ok = ((ll)x*((ll)v[mid].m-v[mid+1].m) <= (ll)v[mid+1].b-v[mid].b);
            if (ok) hi = mid;
            else lo = mid+1;
        }
        return (ll)v[hi].m*x + v[hi].b;
    }

    void undo(int idx) {
        //cout << "UNDO " << endl;
        while (hi > idx) {
            Line cur = h[hi-1];
            if (cur.m == END.m && cur.b == END.b) { --vi; }//cout << "\t\tPOP\n"; }
            else { v[vi++] = cur; }//cout << "\t\tPUSH " << cur.o.m << " " << cur.o.b << '\n'; }
            --hi;
        }
    }
} ch;

void dfs(int u) {
    r[u] = (ll)S[u] + (ll)V[u]*d[u];
    //cout << u << " " << p[u] << endl;
    //for (int v = p[u]; v != 0; v = p[v]) r[u] = min(r[u], (ll)S[u] + (ll)V[u]*(d[u]-d[v]) + r[v]);
    if (u > 1) r[u] = min(r[u], ch.query(V[u]) + (ll)S[u] + (ll)V[u]*d[u]);
    int idx = ch.add({ -d[u], r[u] });
    for (auto v : al[u]) if (v.fi != p[u]) {
        d[v.fi] = d[u] + v.sc;
        p[v.fi] = u;
        dfs(v.fi);
    }
    ch.undo( idx );
}

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    FOR(i,1,N-1){
        int u, v, d; cin >> u >> v >> d;
        al[u].emplace_back(v, d);
        al[v].emplace_back(u, d);
    }

    FOR(i,2,N){ cin >> S[i] >> V[i]; }
    dfs(1);

    FOR(i,2,N) cout << r[i] << (i == N ? '\n' : ' ');
}

• Subtask 1: 40 / 100