제출 #343875

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
343875		emaborevkovic	Harbingers (CEOI09_harbingers)	C++14	100 / 100	277 ms	31452 KiB

harbingers

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second

const ll MAXI = 1e9;

struct line {
	ll dalj, b, cf;
	line() : dalj(0), b(0), cf(0) {};
	line(ll dalj, ll b, ll cf) : dalj(dalj), b(b), cf(cf) {};
	ll calc(ll d, ll s, ll v) {
		return (d-dalj)*v+s+b;
	}
};

const int N = 1e5+11;
pair <ll, ll> a[N]; // a[i].ff = v; a[i].ss = s;
vector <pair<int, ll> > ls[N];
int n;
ll dist[N];
ll res[N];
line c[N];
int p[20][N]; // da znamo na kog ide nasa linija

bool pojede(line x, line y) { // pojede li linija x s manjim a-om y ili ne
	// x ima manji a, veci dalj
	if (x.b <= y.b) return 1;
	if (y.cf*(x.dalj-y.dalj) >= x.b-y.b) return 1;
	return 0;
}

int sjeciste(line x, line y) {
	double ret = x.b-y.b;
	ret /= (x.dalj-y.dalj);
	return ceil(ret);
}

void dfs(int x, int roditelj, ll d, int prev) {
	dist[x] = d;
	c[x].dalj = d; c[x].b = d*a[x].ff+a[x].ss; c[x].cf = 0;
	res[x] = c[x].b;
	if (prev == 0) {
		for (auto susj : ls[x]) {
			if (susj.ff == roditelj) continue;
			dfs(susj.ff, x, d+susj.ss, x);
		}
		return;
	}
	int rj = prev;
	ll brzina = a[x].ff;
	for (int i=19;i>=0;i--) {
		if (p[i][rj] == 0) continue;
		if (c[p[i][rj]].cf > brzina) rj = p[i][rj];
	}
	if (c[rj].cf > brzina) rj = p[0][rj]; 
	res[x] = min(res[x], c[rj].calc(d, a[x].ss, a[x].ff));
	c[x].b = res[x];
	int spoji = prev;
	for (int i=19;i>=0;i--) {
		if (p[i][spoji] == 0) continue;
		if (pojede(c[x], c[p[i][spoji]])) spoji = p[i][spoji];
	}
	if (pojede(c[x], c[spoji])) spoji = p[0][spoji];
	if (spoji == 0) {
		for (auto susj : ls[x]) {
			if (susj.ff == roditelj) continue;
			dfs(susj.ff, x, d+susj.ss, x);
		}
		return;
	}
	p[0][x] = spoji;
	for (int i=1;i<20;i++) p[i][x] = p[i-1][p[i-1][x]];
	c[x].cf = sjeciste(c[x], c[p[0][x]]);
	prev = x;
	if (c[x].cf > MAXI) prev = p[0][x];
	for (auto susj : ls[x]) {
		if (susj.ff == roditelj) continue;
		dfs(susj.ff, x, d+susj.ss, prev);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for (int i=0;i<n-1;i++) {
		int a1, a2;
		ll c1;
		cin >> a1 >> a2 >> c1; a1--; a2--;
		ls[a1].pb(mp(a2, c1));
		ls[a2].pb(mp(a1, c1));
	}
	for (int i=1;i<n;i++) {
		cin >> a[i].ss >> a[i].ff;
	}
	dfs(0, 0, 0, 0);
	for (int i=1;i<n;i++) cout << res[i] << " ";
	return 0;
}

• Subtask 1: 100 / 100