oj.uz

Submission #848635

# Submission time Handle Problem Language Result Execution time Memory
848635 2023-09-13T06:31:10 Z lovrot Harbingers (CEOI09_harbingers) C++17
70 / 100
 1000 ms 23888 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7512 KB Output is correct
2 Correct 3 ms 8028 KB Output is correct
3 Correct 31 ms 14676 KB Output is correct
4 Correct 47 ms 17884 KB Output is correct
5 Correct 57 ms 20816 KB Output is correct
6 Correct 71 ms 23888 KB Output is correct
7 Correct 43 ms 15444 KB Output is correct
8 Execution timed out 1029 ms 18892 KB Time limit exceeded
9 Execution timed out 1040 ms 20376 KB Time limit exceeded
10 Execution timed out 1038 ms 19144 KB Time limit exceeded