Submission #1123835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123835		Mike_Vu	Harbingers (CEOI09_harbingers)	C++20	60 / 100	125 ms	27128 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define ALL(v) v.begin(), v.end()
#define BITJ(x, j) (((x)>>(j))&1)
#define MASK(x) (1LL << (x))

template<typename T> bool maximize(T& x, const T& y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T& x, const T& y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

const int maxn = 1e5+5;

struct Line{
    ll m, b;
    Line(ll _m = 0, ll _b = 0) {
        m = _m;
        b = _b;
    }
    ll cal(ll x) {
        return m*x+b;
    }
}; ///<
ll divi(ll x, ll y) {
    return x/y+(x%y && (x^y)<0);
}
ll inter(Line a, Line b) {
    return divi(b.b-a.b, a.m-b.m);
}
struct change{
    int pos, sz;
    Line a;
    change(int _pos, int _sz, Line _a) {
        pos = _pos;
        sz = _sz;
        a = _a;
    }
};
struct CHT{
    int sz;
    vector<Line> hull;
    vector<change> stk;
    CHT() {
        sz = 0;
        hull.assign(maxn, Line());
    }
    bool check(int pos, Line a) {
//        assert(pos >= 0);
        return inter(hull[pos-1], a) < inter(hull[pos-1], hull[pos]);
    }
    void insline(Line a) {
        //binsearch
        int k = sz;
        if (sz > 1) {
            for (int j = sz/2+1; j; j >>= 1) {
                while (k-j > 0 && check(k-j, a)) k -= j;
            }
        }
        //ins + stk
//        assert(k > -1);
        stk.pb(change(k, sz, hull[k]));
        hull[k] = a;
        sz = k+1;
    }
    void remline() {
        change e = stk.back();
        stk.pop_back();
        sz = e.sz;
        hull[e.pos] = e.a;
    }
    ll query(ll x) {
        int k = 0;
        for (int j = sz>>1; j; j >>= 1) {
            while (k+j < sz && x > inter(hull[k+j-1], hull[k+j])) k += j;
        }
//        assert(k < sz);
//        if (k > 0) cout << "query " << x << ' ' << k << ' ' << inter(hull[k-1], hull[k]) << "\n";
        return hull[k].cal(x);
    }
    void check() {
        for (int i = 0; i < sz; i++) {
            cout << hull[i].m << ' ' << hull[i].b << "\n";
        }
    }
};

int n;
vector<pii> adj[maxn];
int a[maxn], b[maxn];
CHT cht;
ll dis[maxn], dp[maxn];

void dfs(int u, int p) {
//    cout << u << "\n";
//    cht.check();
    if (u != 1) {
        dp[u] = a[u]+b[u]*dis[u];
        if (cht.sz > 0) minimize(dp[u], a[u]+b[u]*dis[u]+cht.query(b[u]));
        cht.insline(Line(-dis[u], dp[u]));
    }
    for (int i = 0; i < (int)adj[u].size(); i++) {
        int v = adj[u][i].fi, w = adj[u][i].se;
        if (v == p) continue;
        dis[v] = dis[u]+w;
        dfs(v, u);
    }
    if (u > 1) cht.remline();
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "task"
//    if (fopen(name".inp", "r")) {
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
    for (int i = 2; i <= n; i++) {
        cin >> a[i] >> b[i];
    }
    dis[1] = dp[1] = 0;
    dfs(1, -1);
    for (int i = 2; i <= n; i++) {
        cout << dp[i] << ' ';
    }
}

• Subtask 1: 60 / 100