Submission #1245773

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245773		enxiayy	Harbingers (CEOI09_harbingers)	C++20	100 / 100	96 ms	32324 KiB

harbingers

#include <bits/stdc++.h>
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define compact(v) v.erase(unique(all(v)), v.end())
#define dbg(v) "[" #v " = " << (v) << "]"
#define el "\n"
#define int long long

using namespace std;
typedef long long ll;
typedef long double ld;

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
long long randRange(long long l, long long r){ return uniform_int_distribution<long long>(l,r)(rng); }

const int N = 2e5 + 5;

int n;
vector < pair<int, ll> > adj[N];
ll dist[N], v[N], c[N], dp[N];

struct Line {
    ll a, b;
    Line (ll a = 0, ll b = 0) : a(a), b(b) {}

    ll f(ll x) {
        return a * x + b;
    }

    ld intersect(Line Other) {
        return 1.0 * (Other.b - b) / (a - Other.a);
    }

    // decreasing slope
    friend bool bad(Line d1, Line d2, Line d3) {
        return d1.intersect(d3) <= d1.intersect(d2);
    }
};

struct CHT {
    vector <Line> hull;
    stack < pair< pair<int, int>, Line> > st;
    int curSZ;

    CHT() {
        hull.clear();
        curSZ = 0;
    }

    void init(int n) {
        hull.resize(n + 5);
    }

    ll query(ll x) {
        int l = 0;
        int r = curSZ - 1;
        ll ans = LLONG_MAX;
        while(l <= r) {
            int mid = (l + r) >> 1;
            ll cur = hull[mid].f(x);
            ans = min(ans, cur);
            if (mid > 0 && hull[mid - 1].f(x) < cur) r = mid - 1;
            else if (mid < curSZ - 1 && hull[mid + 1].f(x) < cur) l = mid + 1;
            else break;
        }
        return ans;
    }

    void add(Line d) {
        int l = 1;
        int r = curSZ - 1;
        int pos = curSZ;
        while(l <= r) {
            int mid = (l + r) >> 1;
            if (bad(hull[mid - 1], hull[mid], d)) {
                pos = mid;
                r = mid - 1;
            }
            else {
                l = mid + 1;
            }
        }

        st.push({{pos, curSZ}, hull[pos]});
        curSZ = pos + 1;
        hull[pos] = d;
    }

    void rollback() {
        if (st.empty()) return;
        auto v = st.top();
        st.pop();
        hull[v.first.first] = v.second;
        curSZ = v.first.second;

    }
};

CHT cht;

void dfs(int i, int par) {
    dp[i] = dist[i] * v[i] + c[i];
//    cerr << i << el;
    ll cur = cht.query(v[i]) + v[i] * dist[i] + c[i];
//    cerr << v[i] << " " << dist[i] << " " << c[i] << el;
    dp[i] = min(dp[i], cur);
//    cout << dp[2] << el;

    cht.add(Line(-dist[i], dp[i]));
    for(auto [v, w] : adj[i]) {
        if (v == par) continue;
        dist[v] = dist[i] + w;
        dfs(v, i);
    }
    cht.rollback();
}


void solve() {
    cin >> n;
    for(int i = 1; i < n; ++i) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        adj[u].eb(v, w);
        adj[v].eb(u, w);
    }

    memset(dp, 0x3f, sizeof(dp));
    dp[1] = 0;

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

    cht.init(n);
    dfs(1, -1);

    for(int i = 2; i <= n; ++i) {
        cout << dp[i] << " ";
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    #define task "task"
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    solve();

    return 0;
}

/*
634 100 611 1526 260
*/

Compilation message (stderr)

harbingers.cpp: In function 'int main()':
harbingers.cpp:150:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:151:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100