Submission #502882

#	Time	Username	Problem	Language	Result	Execution time	Memory
502882		keta_tsimakuridze	Harbingers (CEOI09_harbingers)	C++14	50 / 100	1049 ms	27460 KiB

harbingers

#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pii pair<int,int>
using namespace std;
const int N = 1e5 + 5, mod = 1e9 + 7; // !
int t, v[N], s[N], n;
ll dp[N], h[N];
vector<pii> V[N];
struct line {
	int k, b;
};

vector<line> ts;
ll f(int k,int x,int b) {
	return (ll)k * x + b;
}
double X_(line a, line b) {
//	a.k * x + a.b = b.k * x + b.b
	return (double)(b.b - a.b) / (a.k - b.k);
}
void dfs(int u,int p) {
	// s[u] + (h[u] - h[p]) * v[u] + dp[p] 
	// -h[p] * v[u] + dp[p] + s[u] + h[u] * v[u]
	vector<line> rem;
	dp[u] = 0; 
	int l = 0, r = (int)ts.size() - 2;
	if(ts.size()) dp[u] = min(dp[u], f(ts.back().k, v[u], ts.back().b));
	while(l <= r) {
		int mid = (l + r) / 2;
		if(X_(ts[mid], ts[mid + 1]) <= v[u]) l = mid + 1, dp[u] = min(dp[u], f(ts[mid + 1].k, v[u], ts[mid + 1].b));
		else r = mid - 1;
	}
	dp[u] += (ll) h[u] * v[u] + s[u];
	line new_;
	new_.k = -h[u]; new_.b = dp[u];
	while(ts.size() >= 2) {
		line cur = ts.back();
		line prev = ts[(int)ts.size() - 2];
		if(X_(cur, prev) >= X_(cur, new_)) rem.push_back(cur), ts.pop_back();
		else break;
	}
	ts.push_back(new_);
	for(int i = 0; i < V[u].size(); i++) {
		if(V[u][i].f == p) continue;
		h[V[u][i].f] = h[u] + V[u][i].s;
		dfs(V[u][i].f, u);
	}
	ts.pop_back(); 
	reverse(rem.begin(), rem.end());
	for(int i = 0; i < rem.size(); i++) ts.push_back(rem[i]);
}
main(){
	int n; cin >> n;
	for(int i = 2; i <= n; i++) {
		int u,v, w;
		cin >> u >> v >> w;
		V[u].push_back({v, w});
		V[v].push_back({u, w});
	}
	for(int i = 2; i <= n; i++) {
		int p;
		cin >> s[i] >> v[i];
	}
	dfs(1, 0);
	for(int i = 2; i <= n; i++) cout << dp[i] <<" ";
}

Compilation message (stderr)

harbingers.cpp: In function 'void dfs(int, int)':
harbingers.cpp:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for(int i = 0; i < V[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
harbingers.cpp:52:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for(int i = 0; i < rem.size(); i++) ts.push_back(rem[i]);
      |                 ~~^~~~~~~~~~~~
harbingers.cpp: At global scope:
harbingers.cpp:54:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   54 | main(){
      | ^~~~
harbingers.cpp: In function 'int main()':
harbingers.cpp:63:7: warning: unused variable 'p' [-Wunused-variable]
   63 |   int p;
      |       ^

• Subtask 1: 50 / 100