Submission #1268264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268264		ezdp	Beads and wires (APIO14_beads)	C++20	28 / 100	1096 ms	836 KiB

beads

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

const int MAXN = 2e5;

int n, dp[2][MAXN], ans, a[MAXN], b[MAXN];
vector<array<int, 3>> edges;

void dfs(int u, int p){
	int all = 0;
	dp[1][u] = -1;
	for(int e = a[u]; e <= b[u]; e ++){
		auto [_, v, w] = edges[e];
		if(v == p) continue;
		dfs(v, u);
		{
			int t = 0;
			if(dp[0][v] != -1) t = max(t, dp[0][v]);
			if(dp[1][v] != -1) t = max(t, dp[1][v] + w);
			dp[0][u] += t;
		}
		{
			int t = 0;
			if(dp[0][v] != -1) t = max(t, dp[0][v]);
			if(dp[1][v] != -1) t = max(t, dp[1][v] + w);
			all += t;
		}	
	}
	for(int i = a[u]; i <= b[u]; i ++){
		auto [_, v, w] = edges[i];
		if(v == p) continue;
		int cur = 0;
		int t = 0;
		if(dp[0][v] != -1) t = max(t, dp[0][v]);
		if(dp[1][v] != -1) t = max(t, dp[1][v] + w);
		cur += all - t;
		cur += dp[0][v] + w;
		dp[1][u] = max(dp[1][u], cur);
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 0; i < n - 1; i ++){
		int u, v, w; cin >> u >> v >> w;
		-- u; -- v;
		edges.push_back({u, v, w});
		edges.push_back({v, u, w});
	}
	sort(edges.begin(), edges.end());
	for(int i = 0; i < n; i ++){
		a[i] = -1;
	}
	for(int i = 0; i < 2 * (n - 1); i ++){
		auto [u, v, w] = edges[i];
		if(a[u] == -1) a[u] = i;
		b[u] = i;
	}
	for(int r = 0; r < n; r ++){
		for(int i = 0; i < n; i ++){
			dp[0][i] = dp[1][i] = 0;
		}
		dfs(r, r);
		ans = max(ans, dp[0][r]);
	}
	cout << ans << endl;
}

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