Submission #395305

#	Time	Username	Problem	Language	Result	Execution time	Memory
395305		jbalatos	Harbingers (CEOI09_harbingers)	C++11	10 / 100	61 ms	13952 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;

// {{{
#define rep(i, a, n) for(int i=a; i<n; ++i)
#define per(i, a, n) for(int i=a-1; i>=n; --i)

typedef vector<int> ivec;
typedef long long ll;
typedef pair<int, int> ipair;
typedef vector<vector<ipair> > adjlist;

#define x first
#define y second
#define ITER(A) A.begin(), A.end()
#define REV(A) A.rbegin(), A.rend()
#define pb push_back

#define MAXINT numeric_limits<int>::max()
#define popcount builtin_popcount
#define clz __builtin_clz
#define ctz __builtin_ctz
#define NEW new(nothrow)
// }}}
// AMAX
static inline void amax (int &a, int b) {/*{{{*/
	if (a < b) a = b;
}

static inline void amin (int &a, int b) {
	if (a > b) a = b;
}/*}}}*/

#define MAXN 110

int n, v[MAXN], t[MAXN], d[MAXN], par[MAXN], dp[MAXN];
adjlist adj;

void dfs (int u, int p) {
	par[u] = p;
	for (auto it : adj[u]) {
		int v = it.x, w = it.y;
		if (v != p) {
			d[v] = d[u] + w;
			dfs(v, u);
		}
	}
}

vector<ipair> cht;

void dfs_dp (int u, int p) {
	dp[u] = t[u] + v[u]*d[u];

	if (cht.size() != 0) { /*cht query*/
		int l = 0, r = cht.size() - 1;
		while (l < r) {
			int m = (l+r) / 2;
			ipair e1 = cht[m], e2 = cht[m+1];
			if ( e1.x * v[u] + e1.y <= e2.x * v[u] + e2.y ) l = m+1;
			else r = m;
		}
		dp[u] -= cht[l].x * v[u] + cht[l].y;
	}

	stack<ipair> removed;

	cht.pb({ d[u], -dp[u] });
	while (cht.size() >= 3) {/*cht update*/
		int n = cht.size();
		ipair a = cht[n-3], b = cht[n-2], c = cht[n-1];
		if ( (b.x - c.x) * (b.y - a.y) >= (a.x - b.x) * (c.y - b.y) ) {
			cht.pop_back(); cht.pop_back();
			cht.pb(c);
			removed.push(b);
		} else break;
	}

	for (auto it : adj[u]) if (it.x != p)
		dfs_dp(it.x, u);

	/*cht restore*/
	cht.pop_back();
	while (!removed.empty())
		cht.pb( removed.top() ), removed.pop();
}

int main () {

	scanf("%d", &n);
	adj.resize(n+1);
	rep (i, 0, n-1) {
		int u, v, w; scanf("%d%d%d", &u, &v, &w);
		adj[u].pb({ v, w });
		adj[v].pb({ u, w });
	}
	rep(i, 2, n+1) scanf("%d%d", &t[i], &v[i]);

	//calculate d[]
	d[1] = 0; par[1] = -1;
	dfs(1, -1);
	//tested

	/*
	 * dp[i] : solution for city i
	 * dp[1] = 0
	 * dp[i] = t[i] + v[i]*d[i] - max{j ancestor of k}{ u[i]*d[j] - dp[j] }
	 */
	// O(N^2){{{
//	dp[1] = 0;
//	queue<int> q;
//	for (auto it : adj[1]) q.push(it.x);
//	while (!q.empty()) {
//		int i = q.front(); q.pop();
//
//		dp[i] = t[i] + v[i]*d[i];
//		int temp = (int)-1e9, j = par[i];
//		while (j != -1) {
//			amax( temp, v[i]*d[j] - dp[j] );
//			j = par[j];
//		}
//		dp[i] -= temp;
//
//		for (auto it : adj[i]) if (it.x != par[i])
//			q.push(it.x);
//
//	}/*}}}*/

//	rep (i, 2, n+1) printf("%d ", dp[i]);
//	printf("\n");
	// CHT
	dfs_dp(1, -1);
	

	rep (i, 2, n+1) printf("%d ", dp[i]);

	return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'int main()':
harbingers.cpp:90:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
harbingers.cpp:93:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |   int u, v, w; scanf("%d%d%d", &u, &v, &w);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:97:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   97 |  rep(i, 2, n+1) scanf("%d%d", &t[i], &v[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 100