Submission #552194

#	Time	Username	Problem	Language	Result	Execution time	Memory
552194		QwertyPi	Beads and wires (APIO14_beads)	C++14	100 / 100	328 ms	42992 KiB

beads

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back

using namespace std;
typedef pair<int, int> pii;
const int N = 2e5 + 5;
vector<pii> G[N];
int dp[N][4], W[N], p[N];

void dfs(int v, int par = -1){
	for(auto [i, w] : G[v]){
		if(i == par) continue;
		W[i] = w;
		dfs(i, v);
	}
	// Case 0: do nothing
	int am0 = 0, a0 = 0, a1 = 0;
	vector<int> tune1;
	for(auto [i, w] : G[v]){
		if(i != par) a0 += dp[i][2], a1 += dp[i][2], tune1.pb(dp[i][3] - dp[i][2]);
	}
	sort(tune1.begin(), tune1.end(), greater<>()); if(tune1.size()) a1 += tune1[0];
	dp[v][0] = a0, dp[v][1] = a1;
	// Case 1: p[v]-v-son[v]
	vector<pii> co2, co3;
	for(auto [i, w] : G[v]){
		if(i != par) co2.pb({w + dp[i][0] - dp[i][2], i}), co3.pb({w + dp[i][1] - dp[i][2], i});
	}
	sort(co2.begin(), co2.end(), greater<>());
	sort(co3.begin(), co3.end(), greater<>());
//	for(auto i : co2) cout << i << ' '; cout << endl;
//	for(auto i : co3) cout << i << ' '; cout << endl;
	if(par != -1){
		if(co2.size()) dp[v][2] = max(dp[v][2], a0 + co2[0].fi + W[v]);
		if(co3.size()) dp[v][3] = max(dp[v][3], a0 + co3[0].fi + W[v]);
	}
	// Case 2: son1[v]-v-son2[v]
	if(co2.size() >= 2) dp[v][1] = max(dp[v][1], a0 + (co2[0].se == co3[0].se ? max(co2[0].fi + co3[1].fi, co2[1].fi + co3[0].fi) : co2[0].fi + co3[0].fi));
	dp[v][2] = max(dp[v][0], dp[v][2]);
	dp[v][1] = max(dp[v][0], dp[v][1]);
	dp[v][3] = max(dp[v][1], dp[v][3]);
	dp[v][3] = max(dp[v][2], dp[v][3]);
}

int32_t main(){
	int n;
	cin >> n;
	for(int i = 0; i < n - 1; i++){
		int u, v, we;
		cin >> u >> v >> we;
		G[u].pb({v, we});
		G[v].pb({u, we});
	}
	dfs(1);
//	for(int i = 1; i <= n; i++){
//		cout << i << ": " << dp[i][0] << ' ' << dp[i][1] << ' ' << dp[i][2] << ' ' << dp[i][3] << endl;
//	}
	int ans = 0; for(int j = 0; j < 4; j++) ans = max(ans, dp[1][j]);
	cout << ans << endl;
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(long long int, long long int)':
beads.cpp:14:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   14 |  for(auto [i, w] : G[v]){
      |           ^
beads.cpp:22:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |  for(auto [i, w] : G[v]){
      |           ^
beads.cpp:29:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |  for(auto [i, w] : G[v]){
      |           ^
beads.cpp:20:6: warning: unused variable 'am0' [-Wunused-variable]
   20 |  int am0 = 0, a0 = 0, a1 = 0;
      |      ^~~

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