Submission #848636

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
848636	2023-09-13T06:38:14 Z	lovrot	Harbingers (CEOI09_harbingers)	C++17	70 / 100	1000 ms	22868 KB

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 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("%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

harbingers.cpp: In function 'int main()':
harbingers.cpp:76:38: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll*' {aka 'long long int*'} [-Wformat=]
   76 |  for(int i = 2; i <= n; ++i) scanf("%d%d", S + i, V + i);
      |                                     ~^     ~~~~~
      |                                      |       |
      |                                      int*    ll* {aka long long int*}
      |                                     %lld
harbingers.cpp:76:40: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'll*' {aka 'long long int*'} [-Wformat=]
   76 |  for(int i = 2; i <= n; ++i) scanf("%d%d", S + i, V + i);
      |                                       ~^          ~~~~~
      |                                        |            |
      |                                        int*         ll* {aka long long int*}
      |                                       %lld
harbingers.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
harbingers.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |   scanf("%d%d%d", &u, &v, &d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:76:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |  for(int i = 2; i <= n; ++i) scanf("%d%d", S + i, V + i);
      |                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1

70.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	7516 KB	Output is correct
2	Correct	3 ms	7772 KB	Output is correct
3	Correct	29 ms	13916 KB	Output is correct
4	Correct	51 ms	17060 KB	Output is correct
5	Correct	56 ms	19796 KB	Output is correct
6	Correct	77 ms	22868 KB	Output is correct
7	Correct	40 ms	14672 KB	Output is correct
8	Execution timed out	1006 ms	17408 KB	Time limit exceeded
9	Execution timed out	1066 ms	18444 KB	Time limit exceeded
10	Execution timed out	1043 ms	17612 KB	Time limit exceeded