Submission #439665

#	Time	Username	Problem	Language	Result	Execution time	Memory
439665		soroush	Beads and wires (APIO14_beads)	C++17	100 / 100	295 ms	21484 KiB

beads

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2e5 + 10;
const ll mod = 1e9+7;

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

int n;
int dp[maxn][2] , ans;
vector < pii > adj[maxn];

void dfs(int v , int par = 0){
	for(auto [u , w] : adj[v])if(u ^ par)
		dfs(u , v),
		dp[v][0] += max(dp[u][0] , dp[u][1] + w);
	dp[v][1] = -2e9 - 10;
	for(auto [u , w] : adj[v])if(u ^ par)
		dp[v][1] = max(dp[v][1] , dp[v][0] + w + dp[u][0] - max(dp[u][0] , dp[u][1] + w));
}

void solve(int v , int par = 0){
	ans = max(ans , dp[v][0]);
	int mx[2] = {int(-2e9 - 10) , int(-2e9 - 10)};
	for(auto [u , w] : adj[v]){
		mx[1] = max(mx[1] , dp[u][0] + w - max(dp[u][1] + w , dp[u][0]));
		if(mx[0] < mx[1])swap(mx[0] , mx[1]);
	}
	for(auto [u , w] : adj[v])if(u ^ par){
		int a = dp[u][1] , b = dp[u][0] , c = dp[v][0] , d = dp[v][1];
		bool imx = w + dp[u][0] - max(dp[u][0] , dp[u][1] + w) == mx[0];
		dp[v][1] -= max(dp[u][0] , dp[u][1] + w);
		if(imx)dp[v][1] += mx[1] - mx[0];
		dp[v][0] -= max(dp[u][0] , dp[u][1] + w);
		dp[u][1] += max(dp[v][0] , dp[v][1] + w);
		dp[u][1] = max(dp[u][1] , dp[u][0] + w + dp[v][0]);
		dp[u][0] += max(dp[v][0] , dp[v][1] + w);
		solve(u , v);
		dp[u][1] = a , dp[u][0] = b , dp[v][0] = c , dp[v][1] = d;
	}
}

int32_t main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n;
	for(int i = 1 ; i < n ; i ++){
		int a , b , c;
		cin >> a >> b >> c;
		adj[a].pb({b , c});
		adj[b].pb({a , c});
	}
	dfs(1);
	solve(1);
	cout << ans;
	return(0);
}

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