Submission #1134030

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134030		PagodePaiva	Beads and wires (APIO14_beads)	C++17	13 / 100	15 ms	8008 KiB

beads

#include<bits/stdc++.h>

using namespace std;

const int N = 200010;
const int inf = 1e9;
vector <pair <int, int>> g[N];
int dp[N][2][2];

void dfs(int v, int p, int fg, int fg2){
	if(dp[v][fg][fg2] != -1) return;
	for(auto [x ,w] : g[v]){
		if(x == p) continue;
		dfs(x, v, 0, 0);
		dfs(x, v, 0, 1);
		dfs(x, v, 1, 0);
	}
	if(fg == 1){
		dp[v][1][0] = 0;
		for(auto [x, w] : g[v]){
			if(x == p) continue;
			dp[v][1][0] += min(dp[x][0][0] + w, dp[x][0][1]);
		}
	}
	else{
		int res = 0, pw = 0;
		vector <int> aux;
		for(auto [x, w] : g[v]){
			if(x == p) {
				continue;
			}
			res += min(dp[x][0][0]+w, dp[x][0][1]);
			aux.push_back({-min(dp[x][0][0]+w, dp[x][0][1])+dp[x][1][0]});
		}
		sort(aux.begin(), aux.end());
		if(fg2 == 0) dp[v][0][0] = min(res, (aux.size() > 1 ? res+aux[0]+aux[1] : inf));
		else{
			dp[v][0][1] = (aux.empty() ? inf : res+aux[0]);
		}
	}
}

int main(){
	int n;
	cin >> n;
	int sum = 0;
	for(int i = 1;i < n;i++){
		int a, b, w;
		cin >> a >> b >> w;
		sum += w;
		g[a].push_back({b, w});
		g[b].push_back({a, w});
	}
	int res = inf;
	for(int i = 1;i <= n;i++){
		memset(dp, -1, sizeof dp);
		dfs(i, i, 0, 0);
		res = min(res, dp[i][0][0]);
	}
	cout << sum-res << endl;
}

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