oj.uz

Submission #130718

# Submission time Handle Problem Language Result Execution time Memory
130718 2019-07-16T04:03:48 Z 윤교준(#3170) Harbingers (CEOI09_harbingers) C++14
100 / 100
 176 ms 23160 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define befv(V) ((V)[sz(V)-2])
#define allv(V) ((V).begin()),((V).end())
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
ll operator * (const pll &a, const pll &b) { return a.first*b.second - b.first*a.second; }
ll ccw(const pll &a, const pll &b, const pll &c) { return a*b + b*c + c*a; }

const int MAXN = 100005;

struct CHT {
	vector<pll> V;
	void push(const pll &p) {
		for(; 1 < sz(V) && ccw(befv(V), V.back(), p) >= 0; V.pop_back());
		V.eb(p);
	}
	ll f(int i, ll X) { return V[i].first*X + V[i].second; }
	ll get(ll X) {
		if(V.empty()) return -INFLL;
		ll ret = -INFLL;
		int s = 0, e = sz(V)-1; for(int m; s < e;) {
			m = (s+e) >> 1;
			ll l = f(m, X), r = f(m+1, X);
			if(l <= r) {
				if(ret < r) ret = r;
				s = m+1;
			} else {
				if(ret < l) ret = l;
				e = m-1;
			}
		}
		return max(ret, f(s, X));
	}
} cht[MAXN];
int HI[MAXN], HR[MAXN], Hn;

vector<int> G[MAXN];
int cnt[MAXN], prt[MAXN];

ll L[MAXN], dp[MAXN];

int D[MAXN], E[MAXN];
int A[MAXN], B[MAXN], C[MAXN];

int N;

ll cal(int i, ll X) {
	ll ret = -INFLL;
	for(int l; i;) {
		l = HI[i];
		ll t = cht[l].get(X);
		if(ret < t) ret = t;
		i = prt[HR[l]];
	}
	return ret;
}

void dfs(int i) {
	if(1 < i) dp[i] = -cal(i, E[i]) + D[i] + L[i]*E[i];
	cht[HI[i]].push({L[i], -dp[i]});

	int ni = -1, nc = -1;
	for(int e : G[i]) {
		int v = B[e];
		if(cnt[v] <= nc) continue;
		nc = cnt[v]; ni = v;
	}
	if(ni < 0) return;
	for(int e : G[i]) {
		int v = B[e];
		if(v == ni) continue;
		Hn++;
		HI[v] = Hn; HR[Hn] = v;
		dfs(v);
	}
	HI[ni] = HI[i];
	dfs(ni);
}

void dfsinit(int i) {
	cnt[i] = 1;
	for(int e : G[i]) {
		int v = A[e]^B[e]^i;
		prt[v] = i;
		L[v] = L[i] + C[e];
		G[v].erase(find(allv(G[v]), e));
		dfsinit(v);
		cnt[i] += cnt[v];
	}
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N;
	for(int i = 1; i < N; i++) {
		cin >> A[i] >> B[i] >> C[i];
		G[A[i]].eb(i);
		G[B[i]].eb(i);
	}
	for(int i = 2; i <= N; i++) cin >> D[i] >> E[i];

	dfsinit(1);
	for(int i = 1; i < N; i++) if(prt[A[i]] == B[i]) swap(A[i], B[i]);
	Hn = HI[1] = HR[1] = 1; dfs(1);

	for(int i = 2; i <= N; i++) printf("%lld ", dp[i]);
	puts("");

	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 9 ms 5496 KB Output is correct
3 Correct 64 ms 12920 KB Output is correct
4 Correct 100 ms 16680 KB Output is correct
5 Correct 135 ms 19676 KB Output is correct
6 Correct 167 ms 23160 KB Output is correct
7 Correct 89 ms 13944 KB Output is correct
8 Correct 176 ms 20044 KB Output is correct
9 Correct 166 ms 22264 KB Output is correct
10 Correct 139 ms 21232 KB Output is correct