Submission #1003337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003337		BF001	Beads and wires (APIO14_beads)	C++17	100 / 100	140 ms	43452 KiB

beads

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

#define N 200005
#define int long long
#define fi first
#define se second

typedef pair<int, int> ii;

int n, dp[3][N], res = 0, wi[N], mm[N];
vector<ii> adj[N];

bool cmp(int& a, int& b){
	return a > b;
}

void dfs(int u, int p){
	int d1 = 0, d2 = 0, ma = -1e15;
	vector<int> tmp;
	for (auto x : adj[u]){
		int v = x.fi, w = x.se;
		if (v == p) continue;
		dfs(v, u);
		if (dp[0][v] > 0){
			dp[1][u] += max(dp[0][v] + w, dp[1][v]);
		}
		else dp[1][u] += dp[1][v];
		if (dp[0][v] > 0){
			int mx = max(dp[0][v] + w, dp[1][v]);
			dp[0][u] += mx;
			ma = max(ma, dp[1][v] + w - mx);
		}
		else {
			dp[0][u] += dp[1][v];
			ma = max(ma, w); 
		}
		wi[v] = w;
	}
	dp[0][u] += ma;
	mm[u] = ma;
}

void ud(int p0, int p1, int v){
	int cst = p1;
	if (p0 > 0) cst = max(cst, p0 + wi[v]);
	dp[1][v] += cst;
}

void rr(int u, int p, int p0, int p1){
	res = max(res, dp[1][u]);
	int siz = adj[u].size() - (p != 0);
	vector<int> pre(siz + 2, 0), suf(siz + 2, 0), mpre(siz + 2, 0), msuf(siz + 2, 0);
	mpre[0] = -1e15, msuf[siz + 1] = -1e15;

	if (p != 0){
		if (p0 > 0){
			int mx = max(p0 + wi[u], p1);
			pre[0] += mx;
			mpre[0] = p1 + wi[u] - mx;
		}
		else {
			pre[0] += p1;
			mpre[0] = wi[u];
		}
	}	
	int pos = 0;
	for (auto x : adj[u]){
		int v = x.fi, w = x.se;
		if (v == p) continue;
		pos++;
		pre[pos] = pre[pos - 1];
		mpre[pos] = mpre[pos - 1];
		if (dp[0][v] > 0){
			int mx = max(dp[0][v] + w, dp[1][v]);
			pre[pos] += mx;
			mpre[pos] = max(mpre[pos], dp[1][v] + w - mx);
		}
		else {
			pre[pos] += dp[1][v];
			mpre[pos] = max(mpre[pos], w);
		}
	}

	pos = siz + 1;
	for (int i = adj[u].size() - 1; i >= 0; i--){
		int v = adj[u][i].fi, w = adj[u][i].se;
		if (v == p) continue;
		pos--;
		suf[pos] = suf[pos + 1];
		msuf[pos] = msuf[pos + 1];
		if (dp[0][v] > 0){
			int mx = max(dp[0][v] + w, dp[1][v]);
			suf[pos] += mx;
			msuf[pos] = max(msuf[pos], dp[1][v] + w - mx);
		}
		else {
			suf[pos] += dp[1][v];
			msuf[pos] = max(msuf[pos], w);
		}
	}
	
	pos = 0;

	for (auto x : adj[u]){
		int v = x.fi, w = x.se;
		if (v == p) continue;
		int cst = dp[1][v];
		pos++;
		if (dp[0][v] > 0) cst = max(cst, dp[0][v] + w);
		int p1 = dp[1][u] - cst;
		int p0 = pre[pos - 1] + suf[pos + 1] + max(mpre[pos - 1], msuf[pos + 1]); 
		ud(p0, p1, v);
		rr(v, u, p0, p1);
	}

}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
      
    cin >> n;
    for (int i = 1; i <= n - 1; i++){
    	int u, v, w;
    	cin >> u >> v >> w;
    	adj[u].push_back({v, w});
    	adj[v].push_back({u, w});
    }

    int root = 1;
    dfs(root, 0);
    rr(root, 0, 0, 0);
  	
  	cout << res;

    return 0;
}     

Compilation message (stderr)

beads.cpp: In function 'void dfs(long long int, long long int)':
beads.cpp:19:6: warning: unused variable 'd1' [-Wunused-variable]
   19 |  int d1 = 0, d2 = 0, ma = -1e15;
      |      ^~
beads.cpp:19:14: warning: unused variable 'd2' [-Wunused-variable]
   19 |  int d1 = 0, d2 = 0, ma = -1e15;
      |              ^~

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