oj.uz

Submission #474517

# Submission time Handle Problem Language Result Execution time Memory
474517 2021-09-18T20:48:54 Z pure_mem Harbingers (CEOI09_harbingers) C++14
70 / 100
 1000 ms 25656 KB 
#include <bits/stdc++.h>

#define X first
#define Y second
#define ll long long
#define MP make_pair

using namespace std;

const int N = 1e5 + 123;
const ll INF = 1e18;

typedef pair<ll, ll> Line;

ll f(Line me, ll x) {
	return me.X * x + me.Y;
}

int CHT[N], his[N], ptr, n, sz;
vector< pair<int, ll> > g[N];
ll dp[N], d[N], sp[N], sl[N];
Line cf[N];

ll get(ll x) {
	int l = 1, r = sz - 1;
	while(l <= r) {
		int m = (l + r) / 2;
		if(f(cf[CHT[m]], x) < f(cf[CHT[m + 1]], x))
			r = m - 1;
		else 
			l = m + 1;
	}
	return f(cf[CHT[r + 1]], x);
}

bool bad(int x, int y, int z) {
	return (cf[x].Y - cf[y].Y) * 1.0 / (cf[y].X - cf[x].X) >= (cf[x].Y - cf[z].Y) * 1.0 / (cf[z].X - cf[x].X); 
}

void dfs(int v, int pr) {
	if(pr != -1) {
		dp[v] = get(sp[v]) + sl[v] + sp[v] * d[v];
	}
	cf[v] = {-d[v], dp[v]};
	int tl = ptr;
	while(sz > 1 && bad(CHT[sz - 1], CHT[sz], v))
		his[ptr++] = CHT[sz--];
	CHT[++sz] = v;
	for(pair<int, ll> to: g[v]) {
		if(to.X == pr) continue;
		d[to.X] = d[v] + to.Y, dfs(to.X, v);
	}
	sz--;
	while(ptr > tl)
		CHT[++sz] = his[--ptr];
}

int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n;
	for(int i = 1, x, y, z;i < n;i++) {
		cin >> x >> y >> z;
		g[x].push_back({y, z});
		g[y].push_back({x, z});
	}
	for(int i = 2;i <= n;i++)
		cin >> sl[i] >> sp[i];
	dfs(1, -1);
	for(int i = 2;i <= n;i++)
		cout << dp[i] << " ";
}

Subtask #1
70.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 4 ms 3148 KB Output is correct
3 Correct 47 ms 11080 KB Output is correct
4 Correct 80 ms 15216 KB Output is correct
5 Correct 113 ms 21364 KB Output is correct
6 Correct 131 ms 25656 KB Output is correct
7 Correct 71 ms 12592 KB Output is correct
8 Execution timed out 1092 ms 16588 KB Time limit exceeded
9 Execution timed out 1093 ms 15260 KB Time limit exceeded
10 Execution timed out 1089 ms 17164 KB Time limit exceeded