Submission #741938

#	Time	Username	Problem	Language	Result	Execution time	Memory
741938		marvinthang	Harbingers (CEOI09_harbingers)	C++17	100 / 100	137 ms	25512 KiB

harbingers

/******************************
*    author : @marvinthang    *
*    date :05 / 12 / 2021    *
******************************/

#include <bits/stdc++.h>

using namespace std;

#define  superspeed  ios_base::sync_with_stdio(false);\
                     cin.tie(NULL);\
                     //cout.tie(NULL);
#define  file(name)  freopen(name".inp", "r", stdin);\
                     freopen(name".out", "w", stdout);

const     double PI = 3.1415926535897932384626433832795; // acos((db)-1); atan(-1.0);
const      int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
const  long long oo = 1e18;
const       int MAX = 1e5 + 5;

int numNode;
long long Start[MAX], Speed[MAX], dist[MAX];
vector <pair <int, int>> adj[MAX];

void dfs(int u, int par) {
	for (pair <int, int> &x: adj[u]) {
		int v = x.second, w = x.first;
		if (v == par) continue;
		dist[v] = dist[u] + w;
		dfs(v, u);
	}
}

struct Line {
	long long a, b;
	Line(long long _a = 0, long long _b = 0):
		a(_a), b(_b) {};
} L[MAX];

stack <pair <Line, int>> rb;
int numLine;

bool bad(Line a, Line b, Line c) {
	return (long double) (c.b - a.b) / (a.a - c.a) < (long double) (b.b - a.b) / (a.a - b.a);
}

void add(Line a) {
	int l = 2, r = numLine, res = numLine + 1;
	while (l <= r) {
		int mid = l + r >> 1;
		if (bad(L[mid - 1], L[mid], a)) {
			res = mid;
			r = mid - 1;
		} else l = mid + 1;
	}
	rb.push(make_pair(L[res], numLine));
	numLine = res;
	L[res] = a;
	// for (int i = 1; i <= numLine; ++i) cout << "*" << L[i].a << ' ' << L[i].b << '\n';
	// cout << "============================\n";
}

void rollback() {
	pair <Line, int> x = rb.top(); rb.pop();
	L[numLine] = x.first;
	numLine = x.second;
	// cout << "--rollback--\n";
	// for (int i = 1; i <= numLine; ++i) cout << "*" << L[i].a << ' ' << L[i].b << '\n';
	// cout << "============================\n";
}

long long eval(Line a, long long x) {
	return a.a * x + a.b;
}

long long getMin(long long x) {
	int l = 1, r = numLine;
	long long res = oo;
	while (l <= r) {
		if (l == r) {
			res = min(res, eval(L[l], x));
			break;
		}
		int mid = l + r >> 1;
		long long a = eval(L[mid], x);
		long long b = eval(L[mid + 1], x);
		res = min({res, a, b});
		if (a > b) l = mid + 1; else r = mid - 1;
	}
	return res;
}

// F[v] = (dist[v] - dist[u]) * Speed[v] + Start[v] + F[u]
// 		= (dist[v] * Speed[v] + Start[v]) + (-dist[u] * Speed[v] + F[u])
//      =   		const                 +     a     *     x    +   b
// -dist[u] <<- // Slope <<-

long long F[MAX];

void dfs2(int u, int par) {
	add(Line(-dist[u], F[u]));
	for (pair <int, int> &x: adj[u]) {
		int v = x.second, w = x.first;
		if (v == par) continue;
		F[v] = 1LL * dist[v] * Speed[v] + Start[v] + getMin(Speed[v]);
		dfs2(v, u);
	}
	rollback();
}

int main() {
    superspeed;
	cin >> numNode;
	for (int i = 1; i < numNode; ++i) {
		int u, v, w; cin >> u >> v >> w;
		adj[u].push_back(make_pair(w, v));
		adj[v].push_back(make_pair(w, u));
	}
	for (int i = 2; i <= numNode; ++i)
		cin >> Start[i] >> Speed[i];
	dfs(1, 0);
	dfs2(1, 0);
	for (int i = 2; i <= numNode; ++i) cout << F[i] << ' ';
    return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'void add(Line)':
harbingers.cpp:50:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |   int mid = l + r >> 1;
      |             ~~^~~
harbingers.cpp: In function 'long long int getMin(long long int)':
harbingers.cpp:84:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |   int mid = l + r >> 1;
      |             ~~^~~
harbingers.cpp: In function 'void dfs2(int, int)':
harbingers.cpp:103:21: warning: unused variable 'w' [-Wunused-variable]
  103 |   int v = x.second, w = x.first;
      |                     ^

• Subtask 1: 100 / 100