Submission #561530

#	Time	Username	Problem	Language	Result	Execution time	Memory
561530		maximath_1	Beads and wires (APIO14_beads)	C++11	100 / 100	155 ms	32596 KiB

beads

#include <iostream>
#include <vector>
using namespace std;

#define endl "\n"
#define ll long long
const ll inf = 1e9 + 69;
const int MX = 200005;

int n;
ll parw[MX], dp[MX][2][2];
vector<pair<int, ll> > adj[MX];

void dfs(int nw, int bf = -1){
	if(adj[nw].size() == 1 && bf != -1) return;

	ll res = 0ll;
	ll best_par_mid = -inf;
	ll best_mid = -inf, best_mid2 = -inf;
	int best_mid_child, best_mid2_child;
	ll best_nomid = -inf, best_nomid2 = -inf;
	int best_nomid_child, best_nomid2_child;

	for(pair<int, ll> i : adj[nw]) if(i.first != bf){
		int nx = i.first; ll wt = i.second;
		parw[nx] = wt;

		dfs(nx, nw);

		ll nomidv = max(dp[nx][0][0], dp[nx][1][0]), 
		midv = max(dp[nx][0][1], dp[nx][1][1]) - nomidv;
		res += nomidv;

		if(best_par_mid < midv) best_par_mid = midv;

		ll unuse_midv = dp[nx][0][1] + wt - nomidv;
		if(best_mid < unuse_midv){
			best_mid2 = best_mid;
			best_mid2_child = best_mid_child;
			best_mid = unuse_midv;
			best_mid_child = nx;
		}else if(best_mid2 < unuse_midv){
			best_mid2 = unuse_midv;
			best_mid2_child = nx;
		}

		ll unuse_nomidv = dp[nx][0][0] + wt - nomidv;
		if(best_nomid < unuse_nomidv){
			best_nomid2 = best_nomid;
			best_nomid2_child = best_nomid_child;
			best_nomid = unuse_nomidv;
			best_nomid_child = nx;
		}else if(best_nomid2 < unuse_nomidv){
			best_nomid2 = unuse_nomidv;
			best_nomid2_child = nx;
		}
	}

	dp[nw][0][0] = res;
	dp[nw][0][1] = max(res + max(0ll, best_par_mid), res + best_nomid + best_nomid2);
	if(best_mid_child != best_nomid_child)
		dp[nw][0][1] = max(dp[nw][0][1], res + best_nomid + best_mid);
	else
		dp[nw][0][1] = max(dp[nw][0][1], max(res + best_nomid + best_mid2, res + best_nomid2 + best_mid));

	dp[nw][1][0] = res + parw[nw] + best_nomid;
	dp[nw][1][1] = res + parw[nw] + best_mid;

	return;
}

int main(){
	cin.tie(0) -> sync_with_stdio(0);

	cin >> n; ll tw;
	for(int u, v, i = 1; i < n; i ++){
		cin >> u >> v >> tw;
		adj[u].push_back({v, tw});
		adj[v].push_back({u, tw});
	}

	dfs(1);

	cout << max(dp[1][0][0], dp[1][0][1]) << "\n";
	return 0;
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int)':
beads.cpp:20:22: warning: variable 'best_mid2_child' set but not used [-Wunused-but-set-variable]
   20 |  int best_mid_child, best_mid2_child;
      |                      ^~~~~~~~~~~~~~~
beads.cpp:22:24: warning: variable 'best_nomid2_child' set but not used [-Wunused-but-set-variable]
   22 |  int best_nomid_child, best_nomid2_child;
      |                        ^~~~~~~~~~~~~~~~~
beads.cpp:61:2: warning: 'best_nomid_child' may be used uninitialized in this function [-Wmaybe-uninitialized]
   61 |  if(best_mid_child != best_nomid_child)
      |  ^~
beads.cpp:61:2: warning: 'best_mid_child' may be used uninitialized in this function [-Wmaybe-uninitialized]

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