Submission #77026

#	Time	Username	Problem	Language	Result	Execution time	Memory
77026		samuelfgs96	Beads and wires (APIO14_beads)	C++11	100 / 100	489 ms	40088 KiB

beads

#include<bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const int N = 212345;
int dp[N][2], pai[N];
vector <pii> g[N];
void lul (int u, int pu) {
	for (auto v : g[u]) 
		if (v.fi != pu) {
			pai[v.fi] = u;
			lul(v.fi, u);
		}
	
}
int solve (int u, int cor, int pu) {
	int &ans = dp[u][cor];
	if (ans != -1) return ans;
	ans = -0x3f3f3f3f;
	if (cor == 0) { //os filhos podem ser qualquer coisa
		ans = 0;
		for (auto q : g[u]) {
			int v, w; tie(v, w) = q;
			if (v == pu) continue;
			ans += max(solve(v, 0, u), solve(v, 1, u) + w);
		}
	} else { //um filho tem que ser azul
		vector <int> st[3];
		vector <int> xd;
		for (auto q : g[u]) {
			int v, w; tie(v, w) = q;
			if (v == pu) continue;
			st[0].pb(solve(v, 0, u));
			st[1].pb(solve(v, 1, u) + w);
			st[2].pb(solve(v, 0, u) + w);
			xd.pb(v);
		}
		if (st[0].empty()) return ans;
		int best_id = 0, best = st[2][0] - max(st[0][0], st[1][0]);
		ans = 0;
		for (int i = 0; i < st[0].size(); i++) {
			int value = max(st[0][i], st[1][i]);
			int lucro = st[2][i] - value;
			if (lucro > best) {
				best = lucro;
				best_id = i;
			}
		}
		for (int i = 0; i < st[0].size(); i++)
			if (best_id == i) ans += st[2][i];
			else ans += max(st[0][i], st[1][i]);
	}
	return ans;
}
int ans;
void dfs (int u, int pu, int a, int b) {
	{
		int tmp = 0;
		for (auto q : g[u]) {
			int v, w; tie(v, w) = q;
			if (v == pu) tmp += max(a, b + w);
			else tmp += max(dp[v][0], dp[v][1] + w);
		}
		ans = max(ans, tmp);
	}
	int na = 0, nb = 0;
	for (auto q : g[u]) {
		int v, w; tie(v, w) = q;
		if (v == pu) na += max(a, b + w);
		else na += max(dp[v][0], dp[v][1] + w);
	}
	vector <pii> st[4];
	int ct = 0;
	vector <int> xd;
	for (auto q : g[u]) {
		int v, w; tie(v, w) = q;
		if (v == pu) {
			st[0].eb(a, -1);
			st[1].eb(b + w, -1);
			st[2].eb(a + w, -1);

			st[3].eb(a + w - max(a, b + w), ct++);
			xd.pb(-1);
		} else {
			st[0].eb(dp[v][0], v);
			st[1].eb(dp[v][1] + w, v);
			st[2].eb(dp[v][0] + w, v);

			st[3].eb(dp[v][0] + w - max(dp[v][0], dp[v][1] + w), ct++);
			xd.pb(v);
		}
	}
	sort(st[3].rbegin(), st[3].rend());
	for (int i = 0; i < st[3].size(); i++)
		nb += max(st[0][i].fi, st[1][i].fi);
	for (auto q : g[u]) {
		int v, w; tie(v, w) = q;
		if (v == pu) continue;
		if (st[3].size() == 1) {
			dfs(v, u, na - max(dp[v][0], dp[v][1] + w), -0x3f3f3f3f);
			continue;
		}

		int aqui = nb;
		aqui -= max(dp[v][0], dp[v][1] + w);
		int k = st[3][0].se;
		if (xd[st[3][0].se] == v) { //pegar o segundo
			k = st[3][1].se;
		}
		aqui -= max(st[0][k].fi, st[1][k].fi);
		aqui += st[2][k].fi;
		dfs(v, u, na - max(dp[v][0], dp[v][1] + w), aqui);
	}
}
int main (void) {
	int n; scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int u, v, w; scanf("%d %d %d", &u, &v, &w);
		g[u].eb(v, w);
		g[v].eb(u, w);
	}
	memset (dp, -1, sizeof dp);
	lul(1, 0);
	for (int i = 1; i <= n; i++) {
		solve(i, 0, pai[i]);
		solve(i, 1, pai[i]);
	}

	dfs(1, 0, 0, 0);
	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

beads.cpp: In function 'int solve(int, int, int)':
beads.cpp:50:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < st[0].size(); i++) {
                   ~~^~~~~~~~~~~~~~
beads.cpp:58:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < st[0].size(); i++)
                   ~~^~~~~~~~~~~~~~
beads.cpp: In function 'void dfs(int, int, int, int)':
beads.cpp:103:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < st[3].size(); i++)
                  ~~^~~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:125:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n; scanf("%d", &n);
         ~~~~~^~~~~~~~~~
beads.cpp:127:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v, w; scanf("%d %d %d", &u, &v, &w);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 29 / 29
• Subtask 4: 43 / 43