Submission #386211

#	Time	Username	Problem	Language	Result	Execution time	Memory
386211		ChrisT	Harbingers (CEOI09_harbingers)	C++17	100 / 100	281 ms	32104 KiB

harbingers

#include<bits/stdc++.h>
using namespace std;
const int MN = 1e5 + 5;
#define lc ind<<1
#define rc ind<<1|1
int d[MN], s[MN], v[MN], st[MN], ed[MN], tt;
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 (__int128)(d[j] - d[i]) * (go[k] - go[i]) <= (__int128)(go[j] - go[i]) * (d[k] - d[i]);
}
long long get (vector<int> &v, int x) {
	if (v.empty()) return 1e18;
	int low = 1, high = (int)v.size() - 1, mid, ans = 0;
	while (low <= high) {
		mid = (low + high) / 2;
		if (go[v[mid]] - go[v[mid-1]] <= (long long)x * (d[v[mid]] - d[v[mid-1]])) low = (ans = mid) + 1;
		else high = mid - 1;
	}
	return go[v[ans]] - (long long)d[v[ans]] * x;
}
vector<int> hull[MN<<2];
void update (int ind, int tl, int tr, int l, int r, int i) {
	if (tl > r || tr < l) return;
	if (l <= tl && tr <= r) {
		while ((int)hull[ind].size() > 1 && bad(hull[ind].end()[-2],hull[ind].back(),i))
			hull[ind].pop_back();
		hull[ind].push_back(i);
		return;
	}
	int mid = (tl + tr) / 2;
	update(lc,tl,mid,l,r,i); update(rc,mid+1,tr,l,r,i);
}
long long query (int ind, int tl, int tr, int pos, int x) {
	long long ret = get(hull[ind],x);
	if (tl == tr) return ret;
	int mid = (tl + tr) / 2;
	if (pos <= mid) ret = min(ret,query(lc,tl,mid,pos,x));
	else ret = min(ret,query(rc,mid+1,tr,pos,x));
	return ret;
}
void init (int cur, int p = -1) {
	st[cur] = ++tt;
	for (auto &[i,w] : adj[cur]) if (i != p) {
		d[i] = d[cur] + w;
		init(i,cur);
	}
	ed[cur] = tt;
}
void dfs (int cur, int p = -1) {
	if (~p) go[cur] = query(1,1,tt,st[cur],v[cur]) + (long long)d[cur] * v[cur] + s[cur];
	update(1,1,tt,st[cur],ed[cur],cur);
	for (auto [i,w] : adj[cur]) if (i != p) dfs(i,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]);
	init(1);
	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:59:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |  int n; scanf ("%d",&n);
      |         ~~~~~~^~~~~~~~~
harbingers.cpp:61:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |   int a,b,w; scanf ("%d %d %d",&a,&b,&w);
      |              ~~~~~~^~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:64:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |  for (int i = 2; i <= n; i++) scanf ("%d %d",&s[i],&v[i]);
      |                               ~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100