Submission #446479

#	Time	Username	Problem	Language	Result	Execution time	Memory
446479		lemelisk	Harbingers (CEOI09_harbingers)	C++17	70 / 100	232 ms	65428 KiB

harbingers

//ya prep
#ifndef DBG
#define NDEBUG
#pragma GCC optimize("Ofast")
#pragma GCC target("popcnt")
#endif // DBG
#define _GLIBCXX_FILESYSTEM
#include <bits/stdc++.h>
using namespace std;

#define cn const
#define cauto cn auto
#define FOR(i, from, to) for (int i = (from); i <= int(to); ++i)
#define FORN(i, n) FOR(i, 0, (n) - 1)
#define endl '\n'
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define X F
#define Y S
#define CONT(c) begin(c), end(c)
#define ARR(a, sz) (a), ((a) + (sz))

using ll = long long;
using ull = unsigned long long;
using ulong = unsigned long;
using uint = unsigned;


//#undef DBG
#ifdef DBG
cn bool dbg = true;
#else
cn bool dbg = false;
#endif // DBG

#ifdef MY
cn bool my = true;
#else
cn bool my = false;
#endif // MY

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
template<typename Key>
using ordered_set = __gnu_pbds::tree<Key, __gnu_pbds::null_type, less<Key>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
template<typename Key, typename Value>
using ordered_map = __gnu_pbds::tree<Key, Value, less<Key>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;

template<typename T>
constexpr T sqr(const T& x)
{
    return x * x;
}

template<typename T>
bool rMin(T& v, const T& rval)
{
    if (rval < v) {
        v = rval;
        return true;
    }
    return false;
}

template<typename T>
bool rMax(T& v, const T& rval)
{
    if (v < rval) {
        v = rval;
        return true;
    }
    return false;
}

ll rd()
{
    ll x;
    cin >> x;
    assert(cin);
    return x;
}

/*
template<int Modulo>
struct MOD {
    static cn int M = Modulo;
    uint x;
    constexpr MOD(int val = 0) : x(val) { assert(0 <= val && val < M); }

    constexpr MOD& operator +=(MOD r) {
        x += r.x;
        if (x >= M)
            x -= M;
        return *this;
    }
    friend constexpr MOD operator +(MOD l, MOD r) { return l += r; }

    constexpr MOD& operator *=(MOD r) {
        x = (ll(x) * r.x) % M;
        return *this;
    }
    friend constexpr MOD operator *(MOD l, MOD r) { return l *= r; }

    constexpr MOD& operator -=(MOD r) {
        x -= r.x;
        if (x >= M)
            x += M;
        return *this;
    }
    friend constexpr MOD operator -(MOD l, MOD r) { return l -= r; }

    friend constexpr MOD operator -(MOD a) {
        if (a.x)
            return M - a.x;
        return 0;
    }

    friend ostream& operator <<(ostream& cout, MOD x) { return cout << x.x; }
    friend constexpr bool operator ==(MOD l, MOD r) { return l.x == r.x; }
    friend constexpr bool operator <(MOD l, MOD r) { return l.x < r.x; }
};

namespace std {
template<int Modulo>
struct hash<MOD<Modulo>> {
    size_t operator ()(MOD<Modulo> a) const noexcept { return a.x; }
};
}

using Mersen32Mod = MOD<(1LL << 31) - 1>;
template<>
Mersen32Mod& Mersen32Mod::operator *=(Mersen32Mod r) {
    cauto mul = ll(x) * r.x;
    x = (mul >> 31) + (mul & M);
    if (x >= M)
        x -= M;
    return *this;
}

template<int M>
constexpr MOD<M> binpow(MOD<M> a, ll p)
{
    MOD<M> res = 1;
    while (p != 0) {
        if (p % 2)
            res *= a;
        a *= a;
        p /= 2;
    }
    return res;
}
*/

/*
struct DoubleHash {
    uint r1;
    Mersen32Mod r2;

    DoubleHash(int x = 0) {
        r1 = x;
        r2 = x;
    }
    DoubleHash(initializer_list<int> lst) {
        assert(lst.size() == 2);
        auto it = lst.begin();
        r1 = *it++;
        r2 = *it;
    }

    DoubleHash& operator +=(DoubleHash R) {
        r1 += R.r1;
        r2 += R.r2;
        return *this;
    }
    friend DoubleHash operator +(DoubleHash L, DoubleHash R) {
        return L += R;
    }

    DoubleHash& operator -=(DoubleHash R) {
        r1 -= R.r1;
        r2 -= R.r2;
        return *this;
    }
    friend DoubleHash operator -(DoubleHash L, DoubleHash R) {
        return L -= R;
    }

    DoubleHash& operator *=(DoubleHash R) {
        r1 *= R.r1;
        r2 *= R.r2;
        return *this;
    }
    friend DoubleHash operator *(DoubleHash L, DoubleHash R) {
        return L *= R;
    }

    friend bool operator ==(DoubleHash L, DoubleHash R) {
        return L.r1 == R.r1 && L.r2 == R.r2;
    }

    friend bool operator <(DoubleHash L, DoubleHash R) {
        return mp(L.r1, L.r2) < mp(R.r1, R.r2);
    }

    size_t hash() const {
        return r2.x;
    }
};

namespace std {
template<>
struct hash<DoubleHash> {
    auto operator ()(DoubleHash h) const noexcept { return h.hash(); }
};
}
*/

//#include "limits.h"

cn int N = 1e5 + 1;
vector<pair<int, int>> g[N];
pair<int, int> courier[N];
int n;
ll dp[N];

vector<int> big;

int compress(int big_x)
{
    assert(binary_search(CONT(big), big_x));
    return lower_bound(CONT(big), big_x) - begin(big);
}

struct Line {
    ll k, b;
    ll operator()(int small_x) const {
        assert(0 <= small_x && small_x < int(big.size()));
        return k * big[small_x] + b;
    }
};
cn int R = 1 << 17;
Line t[2 * R];
vector<pair<int, Line>> changes;

int cht_add(Line f)
{
    cn int sz = changes.size();
    int vl = 0, vr = R;
    for (int v = 1; v < 2 * R; ) {
        cauto vm = (vl + vr) / 2;
        if (vm >= int(big.size())) {
            v = 2 * v;
            vr = vm;
            continue;
        }
        auto& vf = t[v];
        cauto l = vf(vl) < f(vl);
        cauto m = vf(vm) < f(vm);
        if (!m) {
            changes.pb({v, vf});
            swap(f, vf);
        }
        if (l ^ m) {
            v = 2 * v;
            vr = vm;
        } else {
            v = 2 * v + 1;
            vl = vm;
        }
    }
    return sz;
}

void undo(int sz)
{
    for (; int(changes.size()) != sz; changes.pop_back()) {
        cauto [v, f] = changes.back();
        t[v] = f;
    }
}

cn ll INF = 2e18;

ll cht_min(int big_x)
{
    cauto small = compress(big_x);
    ll res = INF;
    for (int v = small + R; v; v >>= 1)
        res = min(res, t[v](small));
    return res;
}

void dfs(int v, int pr, int h)
{
    cauto [start, speed] = courier[v];
    dp[v] = ll(h) * speed + cht_min(speed) + start;
    cauto sz = cht_add({-h, dp[v]});
    for (auto [to, len] : g[v])
        if (to != pr)
            dfs(to, v, h + len);
    undo(sz);
}



int main()
{
#ifdef MY
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#else
    #define FILEIO(TASK) do { freopen(TASK".in", "r", stdin); freopen(TASK".out", "w", stdout); } while (false)
    //FILEIO("bicycle");
#endif // MY
    if (!dbg) {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
    }
    cin >> n;
    FORN(i, n - 1) {
        int u, v, len;
        cin >> u >> v >> len;
        g[u].pb({v, len});
        g[v].pb({u, len});
    }
    big.pb(0);
    FOR(v, 2, n) {
        cin >> courier[v].F >> courier[v].S;
        big.pb(courier[v].S);
    }
    sort(CONT(big));
    big.resize(unique(CONT(big)) - begin(big));
    dfs(1, -1, 0);
    FOR(v, 2, n)
        cout << dp[v] << " ";
}

• Subtask 1: 70 / 100