Submission #371469

#	Time	Username	Problem	Language	Result	Execution time	Memory
371469		SuckTinHock	Harbingers (CEOI09_harbingers)	C++17	40 / 100	294 ms	65540 KiB

harbingers

#include <bits/stdc++.h>
#define int long long

using namespace std;
vector< pair<int,int> > G[100005];
int n;
int dp[100005], D[100005], A[100005], B[100005];

struct Line
{
	mutable int k, m, p;
	bool operator<(const Line& o) const { return k > o.k; }
	bool operator<(int x) const { return p < x; }
};

struct CHT : multiset<Line, less<>>
{
    stack< pair< Line, vector<Line> > > S;
    pair< Line, vector<Line> > pseudo;
	static const int INF = LLONG_MAX;
	int div(int a, int b)
	{
		return (a / b) - ((a ^ b) < 0 && a % b);
    }
	bool isect(iterator x, iterator y)
	{
		if (y == end()) return x->p = INF, 0;
		if (x->k == y->k) x->p = x->m < y->m ? INF : -INF;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(int k, int m)
	{
	    S.push(pseudo);
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z))
        {
            if (z != end()) S.top().second.push_back(*z);
            z = erase(z);
        }
		if (x != begin() && isect(--x, y))
        {
            isect(x, y = erase(y));
        }
        else S.top().first = *y;
		while ((y = x) != begin() && (--x)->p >= y->p)
        {
            S.top().second.push_back(*y);
			isect(x, erase(y));
        }
	}
	void revert()
	{
	    if (S.top().first.k || S.top().first.m)
        {
            auto z = insert({S.top().first.k, S.top().first.m, 0}), y = next(z), x = prev(z);
            if (y != end() && y->k == z->k && y->m == z->m) y = erase(y);
            else x = erase(x);
            z = erase(z);
        }
        for (auto v : S.top().second) add(v.k, v.m);
        S.pop();
	}
	int query(int x)
	{
		assert(!empty());
		auto l = *(lower_bound(x));
		return l.k * x + l.m;
	}
} cht;

void DFS(int u, int pre)
{
    for (pair<int,int> T : G[u])
    {
        int v = T.first;
        int w = T.second;
        if (v == pre) continue;
        D[v] += D[u] + w;
        dp[v] = cht.query(B[v]) + A[v] + B[v] * D[v];
        cht.add(-D[v],dp[v]);
        DFS(v,u);
    }
    cht.revert();
}

void xuly()
{
    cht.add(0,0);
    DFS(1,1);
    for (int i = 2; i <= n; ++i) cout << dp[i] << " ";
}

void nhap()
{
    cin >> n;
    int u, v, x;
    for (int i = 1; i < n; ++i)
    {
        cin >> u >> v >> x;
        G[u].push_back({v,x});
        G[v].push_back({u,x});
    }
    for (int i = 2; i <= n; ++i) cin >> A[i] >> B[i];
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //freopen("harbingers.in","r",stdin);
    //freopen("harbingers.out","w",stdout);
    nhap();
    xuly();
    return 0;
}

• Subtask 1: 40 / 100