Submission #386199

#	Time	Username	Problem	Language	Result	Execution time	Memory
386199		ChrisT	Harbingers (CEOI09_harbingers)	C++17	60 / 100	1088 ms	20204 KiB

harbingers

#include<bits/stdc++.h>
using namespace std;
const int MN = 1e5 + 5;
int d[MN], s[MN], v[MN];
long long go[MN];
vector<array<int,2>> adj[MN];
long double intersect (int i, int j) {
	return (long double)(go[j]-go[i]) / (d[j]-d[i]);
}
bool bad (int i, int j, int k) {
	return (long long)(d[j] - d[i]) * (go[k] - go[i]) <= (long long)(go[j] - go[i]) * (d[k] - d[i]);
}
struct CHT {
	vector<int> hull,pts;
	void insert (int x) {
		pts.push_back(x);
		while ((int)hull.size() > 1 && bad(hull.end()[-2],hull.back(),x))
			hull.pop_back();
		hull.push_back(x);
	}
	void erase (int x) {
		assert(pts.back() == x);
		pts.pop_back(); hull.clear();
		for (int i : pts) {
			while ((int)hull.size() > 1 && bad(hull.end()[-2],hull.back(),i))
				hull.pop_back();
			hull.push_back(i);
		}
	}
	long long get (int x) {
		if (hull.empty()) return 1e18;
		int low = 1, high = (int)hull.size() - 1, mid, ans = 0;
		while (low <= high) {
			mid = (low + high) / 2;
			if (go[hull[mid]] - go[hull[mid-1]] <= (long long)x * (d[hull[mid]] - d[hull[mid-1]])) low = (ans = mid) + 1;
			else high = mid - 1;
		}
		return go[hull[ans]] - (long long)d[hull[ans]] * x;
	}
} hull[400];
const int BL = 2000;
void insert (int i) {
	hull[i/BL].insert(i);
}
void erase (int i) {
	hull[i/BL].erase(i);
}
long long get (int x) {
	long long ret = 1e18;
	for (int i = 0; i <= MN / BL; i++) ret = min(ret,hull[i].get(x));
	return ret;
}
void dfs (int cur, int p = -1) {
	if (~p) {
		go[cur] = get(v[cur]) + (long long)d[cur] * v[cur] + s[cur];
	}
	insert(cur);
	for (auto [i,w] : adj[cur]) if (i != p) {
		d[i] = d[cur] + w;
		dfs(i,cur);
	}
	erase(cur);
}
int main () { 
	int n; scanf ("%d",&n);
	for (int i = 1; i < n; i++) {
		int a,b,w; scanf ("%d %d %d",&a,&b,&w);
		adj[a].push_back({b,w}); adj[b].push_back({a,w});
	}
	for (int i = 2; i <= n; i++) scanf ("%d %d",&s[i],&v[i]);
	dfs(1);
	for (int i = 2; i <= n; i++) printf ("%lld%c",go[i]," \n"[i==n]);
	return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'int main()':
harbingers.cpp:65:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |  int n; scanf ("%d",&n);
      |         ~~~~~~^~~~~~~~~
harbingers.cpp:67:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |   int a,b,w; scanf ("%d %d %d",&a,&b,&w);
      |              ~~~~~~^~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:70:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |  for (int i = 2; i <= n; i++) scanf ("%d %d",&s[i],&v[i]);
      |                               ~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 60 / 100