Submission #848635

#	Time	Username	Problem	Language	Result	Execution time	Memory
848635		lovrot	Harbingers (CEOI09_harbingers)	C++17	70 / 100	1040 ms	23888 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; 

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; }
};

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

const int N = 1e5 + 10;

dot HL[N];

ll query(dot d, int lo, int hi) {
	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];
ll S[N], V[N];
ll SIZ[N], DP[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(dot(V[u], 1), 0, SIZ[u]);	
	BIO[u] = 1;

	dot q = dot(-d, DP[u]);
	int ind = SIZ[u];
	for(; ind > 0 && ccw(HL[ind - 1], HL[ind], q) > 0; --ind) {}

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

	for(pair<int, ll> e : G[u]) {
		int v = e.X;
		if(!BIO[v]) {
			SIZ[v] = ind + 1;
			dp(v, d + e.Y);
		}
	}
	HL[ind + 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"[i == n]);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 70 / 100