Submission #869064

#	Time	Username	Problem	Language	Result	Execution time	Memory
869064		sleepntsheep	Harbingers (CEOI09_harbingers)	C++17	10 / 100	126 ms	65300 KiB

harbingers

#include <cstdio>
#include <stack>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll = long long;
using ld = long double;
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false)

#define N 200005
#define ALL(x) x.begin(), x.end()

/*
 * dp[i] = cost from i to 1
 *
 * dp[i] = min p (dp[p] + distance(i, p) + start[i])
 *
 */

int rv[N], c[N], C;
struct line
{
    ll m, c;
    line(ll m, ll c) : m(m), c(c) {}
    ll operator[](ll x) { return m*rv[x]+c; }
};

ostream& operator<<(ostream &out, line k)
{
    out << '{'<<k.m << ", "  <<k.c<<'}';
    return out;
}

struct lichao_rollback
{
    static const size_t M = 2*N;
    vector<line> t;
    stack<pair<int*, int> > S;
    stack<pair<line*, line> > SL;
    vector<int> U, UL;

    lichao_rollback() : t(M, line(0, ll(1e17))) { UL.push_back(-1), U.push_back(-1); }

    void set(int*p, int k) { S.emplace(p, *p), *p = k; }
    void set(line*p, line k) { SL.emplace(p, *p), *p = k; }

    void add(line k, int v, int l, int r)
    {
        int m = (l+r)/2, cl = k[l] <= t[v][l], cm = k[m] <= t[v][m], vl = v+1, vr = v+(m-l+1)*2;
        if (cm) { line tmp = t[v]; set(&t[v], k); k = tmp; }
        if (l == r) return;
        if (cl != cm) add(k, vl, l, m);
        else add(k, vr, m+1, r);
    }

    void add(line k) { save(); add(k, 0, 0, C-1); }

    ll qry(ll x, int v, int l, int r)
    {
        if (l == r) return t[v][x];
        int m = (l+r)/2, vl=v+1, vr=v+(m-l+1)*2;
        if (x <= m) return min(t[v][x], qry(x, vl, l, m));
        return min(t[v][x], qry(x, vr, m+1, r));
    }

    ll qry(ll x) { save(); return qry(x, 0, 0, C-1); }

    void save()
    {
        //UL.push_back(SL.size()), U.push_back(S.size());
    }

    void rollback()
    {
        while (UL.back() < SL.size()) { auto [p, k] = SL.top(); *p = k; SL.pop(); }
        while (U.back() < S.size()) { auto [p, k] = S.top(); *p = k; S.pop(); }
    }
};

int n, s[N], v[N];
ll rt[N], dp[N];
vector<pair<int, int>> g[N];

void compress()
{
    for (int i = 2; i <= n; ++i) c[C++] = v[i];
    sort(c, C+c); C = unique(c, c+C) - c;
    for (int i = 2; i <= n; ++i) rv[lower_bound(c, c+C, v[i]) - c] = v[i];
}

void dfs(int u, int p, lichao_rollback &lc)
{
    dp[u] = s[u] + 1ll*v[u]*rt[u] + lc.qry(lower_bound(c, c+C, v[u]) - c);
    //cerr << "Q " << u << ' ' << lc.qry(v[u]) << ' ' << rt[u] << ' ' << v[u] << ' ' << s[u] << endl;
    dp[1] = 0;
    lc.add(line{-rt[u], dp[u]});
    for (auto [w, v] : g[u]) if (v != p)
    {
        rt[v] = rt[u] + w;
        dfs(v, u, lc);
    }
    lc.rollback();
    lc.rollback();
}

int main()
{
    ShinLena;
    cin >> n;
    for (int u, v, w, i = 1; i < n; ++i) cin >> u >> v >> w, g[u].emplace_back(w, v), g[v].emplace_back(w, u);
    for (int i = 2; i <= n; ++i) cin >> s[i] >> v[i];
    compress();
    lichao_rollback lc;
    dfs(1, 1, lc);
    for (int i = 2; i <= n; ++i) cout << dp[i] << ' ';

    return 0;
}

Compilation message (stderr)

harbingers.cpp: In member function 'void lichao_rollback::rollback()':
harbingers.cpp:83:26: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::stack<std::pair<line*, line> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         while (UL.back() < SL.size()) { auto [p, k] = SL.top(); *p = k; SL.pop(); }
      |                ~~~~~~~~~~^~~~~~~~~~~
harbingers.cpp:84:25: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::stack<std::pair<int*, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         while (U.back() < S.size()) { auto [p, k] = S.top(); *p = k; S.pop(); }
      |                ~~~~~~~~~^~~~~~~~~~

• Subtask 1: 10 / 100