Submission #848655

#	Time	Username	Problem	Language	Result	Execution time	Memory
848655		lovrot	Harbingers (CEOI09_harbingers)	C++17	100 / 100	105 ms	22864 KiB

harbingers

#include <cstdio> 
#include <algorithm>
#include <vector> 
#include <cassert> 

#define MP make_pair
#define X first
#define Y second
#define EB emplace_back

using namespace std;

typedef long long ll; 
typedef long double ld;

struct dot { 
	ll x, y;
	dot() {}
	dot(ll x, ll y) : x(x), y(y) {}
	ll operator* (const dot d) const { return x * d.x + y * d.y; }
};

ld ccw(const dot &a, const dot &b, const dot &c) { return (ld) (b.x - a.x) * (c.y - a.y) - (ld) (b.y - a.y) * (c.x - a.x); }

const int N = 1e5 + 10;

ll SIZ[N], DP[N];
ll S[N], V[N];
dot HL[N];

ll query(int u) {
	dot d = dot(V[u], 1);
	int lo = 0, hi = SIZ[u];
	while(hi - lo > 1) {
		int mi = (lo + hi) / 2;	
		if(HL[mi] * d < HL[mi + 1] * d) hi = mi;
		else lo = mi;
	}
	return min(HL[lo] * d, HL[hi] * d);
}

bool BIO[N];
dot DWN[N];
vector<pair<int, ll>> G[N];

void dp(int u, ll d) {
	if(u != 1) DP[u] = S[u] + V[u] * d + query(u);	
	BIO[u] = 1;

	dot q = dot(-d, DP[u]);
	int lo = -1, hi = SIZ[u];
	while(hi - lo > 1) {
		int mi = (lo + hi) / 2;
		if(ccw(HL[mi], HL[mi + 1], q) >= 0) hi = mi;
		else lo = mi;
	}

	DWN[u] = HL[hi + 1];
	HL[hi + 1] = q;

	for(pair<int, ll> e : G[u]) {
		int v = e.X;
		if(!BIO[v]) {
			SIZ[v] = hi + 1; 
			dp(v, d + e.Y);
		}
	}
	HL[hi + 1] = DWN[u];
}

int n; 

int main() {
	scanf("%d", &n);
	for(int i = 0; i < n - 1; ++i) {
		int u, v, d;
		scanf("%d%d%d", &u, &v, &d);
		G[u].EB(MP(v, d)); 
		G[v].EB(MP(u, d)); 
	}
	for(int i = 2; i <= n; ++i) scanf("%lld%lld", S + i, V + i);	
	SIZ[1] = -1;
	dp(1, 0);
	for(int i = 2; i <= n; ++i) printf("%lld%c", DP[i], "\n\n"[i == n]);
	return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'int main()':
harbingers.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
harbingers.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |   scanf("%d%d%d", &u, &v, &d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:81:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |  for(int i = 2; i <= n; ++i) scanf("%lld%lld", S + i, V + i);
      |                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100