Submission #1263183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263183		amigoo99234	Harbingers (CEOI09_harbingers)	C++20	100 / 100	67 ms	28332 KiB

harbingers

#include <bits/stdc++.h>

using namespace std;

//long long MOD = 1e9 + 7;
const long long MOD = 998244353;
// const long long MOD = 100000007 ;


#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

#define popCnt(x) (__builtin_popcountll(x))
#define int long long
#define ld long double

#define F  first
#define S  second
#define pi  M_PI
#define all(x) x.begin() , x.end()
#define LL long long
#define SZ(v) (int)(v.size())

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
const long long OO = LLONG_MAX / 4, N = 3e5 + 5, M = 1e5 + 5, K = 505;


struct Line {
    LL a, b;
    Line(LL a = 0, LL b = LLONG_MAX) : a(a), b(b) {}
    inline LL F(LL x) const { return a * x + b; }
};

struct State {
    int size;
    int add_pos;
    Line val;
};

template <bool IS_MAX = true>
struct CHT {
public:
    // transform a user-provided line to the internal representation:
    // if IS_MAX==true we store (-a,-b) so the structure (which finds minima)
    // can be reused. Query results are negated back.
    inline Line transform(Line L) const {
        if constexpr (IS_MAX) return Line(-L.a, -L.b);
        else return L;
    }

    long double get_intersec(const Line &x, const Line &y) const {
        // caller must ensure x.a != y.a
        return (long double)(y.b - x.b) / (x.a - y.a);
    }

    vector<Line> line;      // storage for lines (internal/transformed)
    vector<State> order;    // rollback stack
    int cur_size = 0;

    CHT() = default;

    // prepare internal arrays for up to n lines (n = number of adds expected)
    void reload_size(int n) {
        line.assign(n + 3, Line());
        cur_size = 0;
        order.clear();
    }

    // add a line (user gives normal line). Slopes must be strictly increasing.
    void add_line(Line userL) {
        Line x = transform(userL);

        // binary search to find insertion position (keeps intersections monotone)
        int low = 1, high = cur_size - 1;
        int pos = cur_size;

        // If cur_size==0 -> pos stays 0 -> we will set line[0] = x
        while (low <= high) {
            int mid = (low + high) >> 1;
            // ensure we don't divide by zero inside get_intersec calls:
            // mid-1 and mid are valid indices and should have different slopes
            long double inter1 = get_intersec(line[mid - 1], line[mid]);
            long double inter2 = get_intersec(line[mid], x);
            if (inter1 >= inter2) {
                pos = mid;
                high = mid - 1;
            } else low = mid + 1;
        }

        // save previous state for rollback
        if ((int)order.size() == 0 || order.back().size != cur_size || order.back().add_pos != pos || !(order.back().val.a == line[pos].a && order.back().val.b == line[pos].b)) {
            order.push_back({cur_size, pos, line[pos]});
        } else {
            // still push to preserve 1:1 with add operations (safer)
            order.push_back({cur_size, pos, line[pos]});
        }

        cur_size = pos + 1;
        line[pos] = x;
    }

    // query at x (user x). Works for arbitrary x (binary search on intersections).
    // returns the actual requested value (min or max, depending on template)
    LL Get(LL xval) const {
        if (cur_size == 0) return LLONG_MAX; // no lines
        int low = 1, high = cur_size - 1, pos = 0;
        while (low <= high) {
            int mid = (low + high) >> 1;
            long double inter = get_intersec(line[mid - 1], line[mid]);
            if (inter <= (long double)xval) {
                pos = mid;
                low = mid + 1;
            } else high = mid - 1;
        }
        LL raw = line[pos].F(xval);
        if constexpr (IS_MAX) return -raw; // negate back for max
        else return raw;                  // already min
    }

    // rollback last add
    void rollback() {
        if (order.empty()) return;
        State s = order.back();
        order.pop_back();

        cur_size = s.size;
        line[s.add_pos] = s.val;
    }
};


CHT<true> cht;
int n;
vector<int> v, c;
vector<vector<pair<int, int>>> adj;

vector<int> dp;
void dfs(int node , int p = -1 , int d = 0)
{
    if(p == -1) dp[node] = 0;
    else dp[node] = cht.Get(v[node]) + v[node] * d + c[node];

    cht.add_line(Line(-d , dp[node]));

    for(auto [child , len] : adj[node])
    {
        if(child == p)continue;
        dfs(child , node , d + len);
    }
    cht.rollback();
}

signed main() {
    fast;


//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);

    cin >> n;
    dp = v = c = vector<int>(n);
    adj.resize(n);

    for (int i = 0; i < n - 1; ++i) {
        int u, vv, d;
        cin >> u >> vv >> d;
        u--;
        vv--;
        adj[u].emplace_back(vv, d);
        adj[vv].emplace_back(u, d);
    }

    for (int i = 1; i < n; ++i) {
        cin >> c[i] >> v[i];
    }


    cht.reload_size(n);
    dfs(0);

    for(int i = 1 ; i < n ; i++) cout << dp[i] << " ";
    cout<<'\n';



}

• Subtask 1: 100 / 100