Submission #1224951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224951		nrg_studio	Harbingers (CEOI09_harbingers)	C++20	0 / 100	96 ms	25524 KiB

harbingers

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

#define ll long long
#define pb push_back
#define pii pair<ll,ll>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define all(x) x.begin(),x.end()
#define vec vector

const int MAX_N = 100000, l2d = 18;
double lift[MAX_N+1][l2d];
vec<pair<int,int>> adj[MAX_N];
int spd[MAX_N], start[MAX_N];
int par[MAX_N];
ll dist[MAX_N], ans[MAX_N];

double isect(pii a, pii b) {return (double)(a.s-b.s)/(b.f-a.f);}

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

    int n; 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=1;i<n;i++) {cin >> start[i] >> spd[i];}
    spd[0] = start[0] = 0;

    stack<int> todo, go_back;
    vector<pii> hull;
    todo.push(0);
    dist[0] = ans[0] = 0;

    while (todo.size()) {
        int cur = todo.top(); todo.pop();
        ans[cur] = 0;

        if (hull.size()) {
            int lo = 0, hi = hull.size()-1, mid = (lo+hi)/2, res = 0;
            while (lo <= hi) {
                int i = __builtin_clzll(1)-__builtin_clzll(hull.size()-mid);
                double pt = min(lift[hull.size()-1][i],lift[mid+(1<<i)-1][i]);
                if (pt<=spd[cur]) {res = mid; lo = mid+1;}
                else {hi = mid-1;}
                mid = (lo+hi)/2;
            }

            //cout << cur+1 << ' ' << res << '\n';
            ans[cur] = hull[res].f*spd[cur]+hull[res].s + dist[cur]*spd[cur]+start[cur];
        }
        hull.pb({-dist[cur],ans[cur]});

        int sz = hull.size();
        if (sz>1) {
            int lo = 0, hi = hull.size()-3, mid = (lo+hi)/2, res = hull.size()-2;
            while (lo <= hi) {
                if (isect(hull.back(),hull[mid])<=isect(hull[mid],hull[mid+1])) {
                    res = mid; hi = mid-1;
                } else {lo = mid+1;}
                mid = (lo+hi)/2;
            } lift[sz-1][0] = isect(hull.back(),hull[res]);
            //cout << cur+1 << ' ' << res << ' ';
            //cout << lift[sz-1][0] << '\n';
        } else {
            lift[sz-1][0] = 0;
        }

        for (int i=1;i<l2d;i++) {
            lift[sz-1][i] = (sz>=(1<<i) ? min(lift[sz-1][i-1],lift[sz-1-(1<<(i-1))][i-1]) : 0);
        }
        int last = -1;
        for (auto[x,d] : adj[cur]) {
            if (x!=par[cur]) {
                par[x] = cur; dist[x] = dist[cur]+d;
                todo.push(x);
                if (last==-1) {last = x;}
            }
        }
        if (last!=-1) {go_back.push(last);}
        //cout << cur << ' ' << last << '\n';

        if (adj[cur].size()==1 && cur!=0) {hull.pop_back();}
        while (go_back.size() && go_back.top()==cur) {
            cur = par[cur]; go_back.pop();
            hull.pop_back();
        }
    }
    for (int i=1;i<n;i++) {cout << ans[i] << ' ';}
    /*
    minimize: dp[j]+(dist[i]-dist[j])spd[i]+start[i]
    -dist[j]spd[i]+dp[j] + dist[i]spd[i]+start[i]
    */
}

• Subtask 1: 0 / 100