oj.uz

Submission #339087

# Submission time Handle Problem Language Result Execution time Memory
339087 2020-12-24T15:07:49 Z lohacho Harbingers (CEOI09_harbingers) C++14
0 / 100
 202 ms 50524 KB 
#include <bits/stdc++.h>

using namespace std;

using LL = long long;
vector<vector<LL>> cht((LL)1e5, vector<LL>(3));
vector<pair<vector<LL>, LL>> era;
LL top;

inline LL getc(vector<LL> A, vector<LL> B){
	return (B[2] - A[2]) / (A[1] - B[1]) + ((B[2] - A[2]) % (A[1] - B[1]) > 0);
}

void push(LL A, LL B){
	cht[top++] = {-(LL)1e18, A, B};
	if(top >= 2){
		cht[top - 1][0] = getc(cht[top - 2], cht[top - 1]);
	}
	if(top >= 3){
		int s = 2, e = top - 1, mid;
		while(s < e){
			mid = (s + e) >> 1;
			if(cht[mid][0] >= getc(cht[mid - 1], cht[top - 1])){
				e = mid;
			}
			else{
				s = mid + 1;
			}
		}
		era.push_back({cht[s], top - 1});
		cht[s] = cht[top - 1], top = s + 1;
		if(top >= 2){
			cht[top - 1][0] = getc(cht[top - 2], cht[top - 1]);
		}
	}
}

LL get(LL x){
	vector<LL> vc = {x + 1, -(LL)1e18, -(LL)1e18};
	LL pos = lower_bound(cht.begin(), cht.begin() + top, vc) - cht.begin() - 1;
	return cht[pos][1] * x + cht[pos][2];
}

void del(){
	cht[top - 1] = era.back().first, top = era.back().second;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	LL N;
	cin >> N;
	vector<vector<pair<LL, LL>>> way(N);
	for(LL i = 0; i < N - 1; ++i){
		LL a, b, c; cin >> a >> b >> c; --a; --b;
		way[a].push_back({b, c}), way[b].push_back({a, c});
	}
	vector<pair<LL, LL>> val(N);
	for(LL i = 1; i < N; ++i){
		cin >> val[i].first >> val[i].second;
	}
	vector<LL> sum(N), chk(N), dp(N);
	function<void(LL, LL)> dfs = [&](LL x, LL dis){
		sum[x] = dis;
		chk[x] = 1;
		if(x){
			dp[x] = get(val[x].second) + val[x].first + val[x].second * sum[x];
		}
		else dp[x] = 0;
		push(-sum[x], dp[x]);
		for(auto&nxt:way[x]){
			if(!chk[nxt.first]){
				dfs(nxt.first, dis + nxt.second);
			}
		}
		del();
	};
	dfs(0, 0);
	for(LL i = 1; i < N; ++i){
		cout << dp[i] << ' ';
	}
	return 0;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 5868 KB Output isn't correct
2 Incorrect 11 ms 6636 KB Output isn't correct
3 Incorrect 100 ms 17884 KB Output isn't correct
4 Incorrect 145 ms 23388 KB Output isn't correct
5 Incorrect 162 ms 29104 KB Output isn't correct
6 Runtime error 202 ms 34384 KB Memory limit exceeded
7 Runtime error 79 ms 31976 KB Execution killed with signal 8 (could be triggered by violating memory limits)
8 Runtime error 170 ms 47964 KB Execution killed with signal 8 (could be triggered by violating memory limits)
9 Runtime error 131 ms 42204 KB Execution killed with signal 8 (could be triggered by violating memory limits)
10 Runtime error 168 ms 50524 KB Execution killed with signal 8 (could be triggered by violating memory limits)