Submission #337064

#	Time	Username	Problem	Language	Result	Execution time	Memory
337064		Vince729	Harbingers (CEOI09_harbingers)	C++11	50 / 100	1101 ms	26732 KiB

harbingers

#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<complex>
#include<cassert>
#include<stack>
using namespace std;

typedef long long ll;
typedef complex<double> pt;
typedef pair<ll, ll> pii;
#define x() real()
#define y() imag()
#define smx(a, b) a = max(a, b)
#define smn(a, b) a = min(a, b)
#define in(mp, v) (mp.find(v) != mp.end())

const int MAXN = 100005;
const int MOD = 1000000007;

class cht {
    private:
        vector<long long> m, b;
        int sz = 0;
        bool test(int i, int j, ll mk, ll bk) {
            return (b[j]-b[i])*(mk-m[i]) > (bk-b[i])*(m[j]-m[i]);
        }
        long long eval(int i, long long x) {
            assert(i < sz);
            return m[i]*x+b[i];
        }

    public:
        pair<int, pii> insert(long long mv, long long bv) {
            int rem = 0;
            while (sz >= 2 && !test(sz-2, sz-1, mv, bv)) {
                sz--;
                rem++;
            }
            if (rem == 0) {
                if (sz == m.size()) {
                    m.push_back(mv); b.push_back(bv);
                } else {
                    m[sz] = mv;
                    b[sz] = bv;
                }
                sz++;
                return {0, {0, 0}};
            }
            pii old = {m[sz], b[sz]};
            m[sz] = mv; b[sz] = bv;
            sz++;
            return {rem, old};
        }
        long long query(long long x) {
            int l = 0, r = sz-2;
            while (l <= r) {
                int mid = (l+r)/2;
                if (eval(mid, x) > eval(mid+1, x)) {
                    l = mid+1;
                } else {
                    r = mid-1;
                }
            }
            return eval(l, x);
        }
        void rest(int cnt, ll mv, ll bv) {
            if (cnt == 0) {
                sz--;
                return;
            }
            m[sz-1] = mv; b[sz-1] = bv;
            sz += cnt-1;
        }
        void popLast() {
            m.pop_back();
            b.pop_back();
            sz--;
        }
};

int n;
vector<pair<int, ll>> adj[MAXN];
ll si[MAXN], vi[MAXN];
cht ch;
ll ans[MAXN];

void dfs(int x, int p, ll d) {
    if (x != 1) ans[x] = ch.query(vi[x])+d*vi[x]+si[x];
    auto rem = ch.insert(-d, ans[x]);
    for (auto pv : adj[x]) {
        if (pv.first != p) {
            dfs(pv.first, x, d+pv.second);
        }
    }
    ch.rest(rem.first, rem.second.first, rem.second.second);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 0; i < n-1; i++) {
        int u, v; ll d; cin >> u >> v >> d;
        adj[u].push_back({v, d});
        adj[v].push_back({u, d});
    }
    for (int i = 2; i <= n; i++) {
        cin >> si[i] >> vi[i];
    }
    dfs(1, 1, 0);
    for (int i = 2; i <= n; i++) {
        cout << ans[i];
        if (i < n) cout << " ";
    }
    cout << endl;
    return 0;
}

Compilation message (stderr)

harbingers.cpp: In member function 'std::pair<int, std::pair<long long int, long long int> > cht::insert(long long int, long long int)':
harbingers.cpp:46:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |                 if (sz == m.size()) {
      |                     ~~~^~~~~~~~~~~

• Subtask 1: 50 / 100