Submission #848638

#	Time	Username	Problem	Language	Result	Execution time	Memory
848638		lovrot	Harbingers (CEOI09_harbingers)	C++17	90 / 100	84 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; 

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(const dot &a, const dot &b, const dot &c) { return (b.x - a.x) * (c.y - a.y) - (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("%d%d", 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:80:38: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll*' {aka 'long long int*'} [-Wformat=]
   80 |  for(int i = 2; i <= n; ++i) scanf("%d%d", S + i, V + i);
      |                                     ~^     ~~~~~
      |                                      |       |
      |                                      int*    ll* {aka long long int*}
      |                                     %lld
harbingers.cpp:80:40: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'll*' {aka 'long long int*'} [-Wformat=]
   80 |  for(int i = 2; i <= n; ++i) scanf("%d%d", S + i, V + i);
      |                                       ~^          ~~~~~
      |                                        |            |
      |                                        int*         ll* {aka long long int*}
      |                                       %lld
harbingers.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
harbingers.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   scanf("%d%d%d", &u, &v, &d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:80:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |  for(int i = 2; i <= n; ++i) scanf("%d%d", S + i, V + i);
      |                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 90 / 100