Submission #337035

#	Time	Username	Problem	Language	Result	Execution time	Memory
337035		Vince729	Harbingers (CEOI09_harbingers)	C++11	0 / 100	1098 ms	24024 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, int k) {
            return (b[j]-b[i])*(m[k]-m[i]) > (b[k]-b[i])*(m[k]-m[i]);
        }
        long long eval(int i, long long x) {
            return m[i]*x+b[i];
        }

    public:
        int insert(long long mv, long long bv) {
            sz++;
            m.push_back(mv); b.push_back(bv);
            int rem = 0;
            while (sz >= 3 && !test(sz-3, sz-2, sz-1)) {
                swap(m[sz-1], m[sz-2]);
                swap(b[sz-1], b[sz-2]);
                sz--;
                rem++;
            }
            return rem;
        }
        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) {
            m.erase(m.end()-cnt-1);
            b.erase(b.end()-cnt-1);
            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];
    int 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);
}

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] << " ";
    return 0;
}

• Subtask 1: 0 / 100