oj.uz

Submission #473747

# Submission time Handle Problem Language Result Execution time Memory
473747 2021-09-16T04:26:15 Z jalsol Harbingers (CEOI09_harbingers) C++17
60 / 100
 1000 ms 32524 KB 
// looking to shine brighter in this world...

#define TASK "harbingers"

#ifdef LOCAL
#include "local.h"
#else
#include <bits/stdc++.h>
#define debug(...)
#define DB(...)
#endif

using namespace std;

using ll = long long;
using ld = long double;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fi first
#define se second

#define For(i, l, r) for (int i = (l); i <= (r); ++i)
#define Ford(i, r, l) for (int i = (r); i >= (l); --i)
#define Rep(i, n) For (i, 0, (n) - 1)
#define Repd(i, n) Ford (i, (n) - 1, 0)
#define Fe(...) for (auto __VA_ARGS__)

template <class C> inline int isz(const C& c) { return static_cast<int>(c.size()); }
template <class T> inline bool chmin(T& a, const T& b) { return (a > b) ? a = b, true : false; }
template <class T> inline bool chmax(T& a, const T& b) { return (a < b) ? a = b, true : false; }

const bool __initialization = []() {
    cin.tie(nullptr)->sync_with_stdio(false);
    if (fopen(TASK".inp", "r")) {
        (void)(!freopen(TASK".inp", "r", stdin));
        (void)(!freopen(TASK".out", "w", stdout)); }
    cout << setprecision(12) << fixed;
    return true;
}();

constexpr ld eps = 1e-9;
constexpr int inf = 1e9;
constexpr ll linf = 1e18;

// =============================================================================

constexpr int maxn = 1e5 + 5;

struct Data {
    int v; ll c;

    Data() : v(0), c(0) {}
    Data(int _v, ll _c) : v(_v), c(_c) {}
};

struct Town {
    ll init, speed;

    Town() : init(0), speed(0) {}
    Town(ll _i, ll _s) : init(_i), speed(_s) {}
};


constexpr long long isCHTQuery = -(1LL << 62);

struct Line {
    long long m, b;
    mutable std::function<const Line*()> nxt;

    Line(long long _m, long long _b) : m(_m), b(_b) {}

    bool operator<(const Line& o) const {
        if (o.b != isCHTQuery) return m < o.m;

        const Line* s = nxt();
        if (!s) return false;

        return b - s->b < (s->m - m) * o.m;
    }
};

struct CHT : public std::multiset<Line> {
    bool bad(iterator y) {
        if (size() == 1) return false;

        auto z = next(y);

        // y is the first line
        if (y == begin()) {
            // parallel, y is under z
            return (y->m == z->m) && (y->b <= z->b);
        }

        auto x = prev(y);

        // y is the last line
        if (z == end()) {
            // parallel, y is under x
            return (y->m == x->m) && (y->b <= x->b);
        }

        // x.isect(y) >= y.isect(z)
        return (x->b - y->b) * (z->m - y->m) >= (y->b - z->b) * (y->m - x->m);
    }

    void add(long long m, long long b) {
        auto y = insert({ m, b });

        if (bad(y)) {
            erase(y);
            return;
        }

        // delete lines on the right
        while (next(y) != end() && bad(next(y))) {
            erase(next(y));
        }

        y->nxt = [=] { return next(y) == end() ? 0 : &*next(y); };

        // delete lines on the left
        while (y != begin() && bad(prev(y))) {
            erase(prev(y));
        }

        if (y != begin()) {
            prev(y)->nxt = [=] { return &*y; };
        }
    }

    long long query(long long x) {
        auto l = *lower_bound(Line(x, isCHTQuery));
        return l.m * x + l.b;
    }
};

int n;
vector<Data> g[maxn];
Town a[maxn];

ll dist[maxn];
ll dp[maxn];

struct Sub1 {
    int par[maxn];

    void Dfs(int u) {
        for (int v = par[u]; v; v = par[v]) {
            chmin(dp[u], dp[v] + a[u].init + a[u].speed * (dist[u] - dist[v]));
        }

        Fe (&[v, c] : g[u]) {
            if (par[v] != -1) continue;

            par[v] = u;
            dist[v] = dist[u] + c;

            Dfs(v);
        }
    }

    void solve() {
        memset(par + 1, -1, 4 * n);
        memset(dp + 1, 0x3f, 8 * n);

        par[1] = 0;
        dp[1] = 0;

        Dfs(1);

        For (i, 2, n) {
            cout << dp[i] << " \n"[i == n];
        }
    }
};

struct Sub2 {
    CHT hull;

    void Dfs(int u, int p) {
        dp[u] = a[u].init + a[u].speed * dist[u]
                - hull.query(a[u].speed);

        hull.add(dist[u], -dp[u]);

        Fe (&[v, c] : g[u]) {
            if (v == p) continue;
            dist[v] = dist[u] + c;
            Dfs(v, u);
        }
    }

    void solve() {
        // dp[u] + a[v].init + a[v].speed * (dist[v] - dist[u])
        // dp[u] + s[v] + v[v] * (d[v] - d[u])
        // dp[u] + s[v] + v[v] * d[v] - v[v] * d[u]
        // s[v] + v[v] * d[v] - v[v] * d[u] + dp[u]
        // s[v] + v[v] * d[v] + f(v[v])

        hull.add(0, 0);
        Dfs(1, -1);

        For (i, 2, n) {
            cout << dp[i] << " \n"[i == n];
        }
    }
};

signed main() {
    cin >> n;

    int maxi = 0;
    Rep (_, n - 1) {
        int u, v; ll c; cin >> u >> v >> c;
        g[u].emplace_back(v, c);
        g[v].emplace_back(u, c);

        chmax(maxi, isz(g[u]));
        chmax(maxi, isz(g[v]));
    }

    For (i, 2, n) cin >> a[i].init >> a[i].speed;

    if (maxi == 2) {
        make_unique<Sub2>()->solve();
    }
    else {
        make_unique<Sub1>()->solve();
    }

    return 0;
}

Subtask #1
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4556 KB Output is correct
2 Correct 5 ms 4940 KB Output is correct
3 Correct 61 ms 16452 KB Output is correct
4 Correct 96 ms 23356 KB Output is correct
5 Correct 126 ms 27048 KB Output is correct
6 Correct 171 ms 32524 KB Output is correct
7 Execution timed out 1079 ms 9728 KB Time limit exceeded
8 Execution timed out 1079 ms 12412 KB Time limit exceeded
9 Execution timed out 1088 ms 12084 KB Time limit exceeded
10 Execution timed out 1087 ms 12084 KB Time limit exceeded