제출 #1268271

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268271		ezdp	구슬과 끈 (APIO14_beads)	C++20	100 / 100	101 ms	27572 KiB

beads

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

template<class T> using matrix = vector<vector<T>>;

const int MAXN = 2e5;
const int INF = 1e15;

int n, dp[2][MAXN], ans;
pair<int, int> subs[MAXN];
matrix<pair<int, int>> G;

void dfs_dp(int u, int p){
	dp[1][u] = -INF;
	subs[u] = {-INF, -INF};
	for(auto [v, w] : G[u]){
		if(v == p) continue;
		dfs_dp(v, u);
		int t = max(dp[0][v], (dp[1][v] != -INF ? dp[1][v] + w : 0LL));
		dp[0][u] += t;
		int my_sub = (dp[0][v] + w) - t;
		if(my_sub > subs[u].first){ subs[u].second = subs[u].first; subs[u].first = my_sub; }
		else if(my_sub > subs[u].second){ subs[u].second = my_sub; }
	}
	dp[1][u] = dp[0][u] + subs[u].first;
}

void dfs_ans(int u, int p){
	ans = max(dp[0][u], ans);
	for(auto [v, w] : G[u]){
		if(v == p) continue;
		auto a = dp[0][u];
		auto b = dp[1][u];
		auto c = dp[0][v];
		auto d = dp[1][v];
		auto e = subs[u];
		
		int tu = max(dp[0][v], (dp[1][v] != -INF ? dp[1][v] + w : 0LL));
		dp[0][u] -= tu;
		if((dp[0][v] + w) - tu == subs[u].first) dp[1][u] = dp[0][u] + subs[u].second;
		else dp[1][u] = dp[0][u] + subs[u].first;
		
		int tv = max(dp[0][u], (dp[1][u] != -INF ? dp[1][u] + w : 0LL));
		dp[0][v] += tv;
		int my_sub = (dp[0][u] + w) - tv;
		if(my_sub > subs[v].first){ subs[v].second = subs[v].first; subs[v].first = my_sub; }
		else if(my_sub > subs[v].second){ subs[v].second = my_sub; }
		dp[1][v] = dp[0][v] + subs[v].first;
		
		dfs_ans(v, u);
		
		dp[0][u] = a;
		dp[1][u] = b;
		dp[0][v] = c;
		dp[1][v] = d;
		subs[u] = e;
	}
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	G.resize(n);
	for(int i = 0; i < n - 1; i ++){
		int u, v, w; cin >> u >> v >> w;
		-- u; -- v;
		G[u].push_back({v, w});
		G[v].push_back({u, w});
	}
	dfs_dp(0, 0);
	dfs_ans(0, 0);
	cout << ans << endl;
}

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