Submission #162291

#	Time	Username	Problem	Language	Result	Execution time	Memory
162291		amoo_safar	Beads and wires (APIO14_beads)	C++14	100 / 100	343 ms	40752 KiB

beads

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
typedef pair<pll, pll> node;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const ll Mod = 1000000007LL;
const int Maxn = 2e5 + 10;
const int Maxk = 60;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

vector<pll> G[Maxn];

ll dp1[Maxn], dp2[Maxn];

ll DFS(ll u, ll p){
	ll adj;
	ll mx = -Inf;
	for(auto ed : G[u]){
		adj = ed.F;
		if(adj == p) continue;
		DFS(adj, u);
		dp1[u] += max(dp1[adj], dp2[adj] + ed.S);
		mx = max(mx, ed.S + dp1[adj] - max(dp1[adj], dp2[adj] + ed.S));
	}
	dp2[u] = dp1[u] + mx;
}

ll dpu1[Maxn], dpu2[Maxn];
ll pssm[Maxn], psmx[Maxn];
ll sfsm[Maxn], sfmx[Maxn];
ll ans = 0;
ll dfs(ll u, ll p, ll w){
	vector< pair<pll, pll> > S;
	ll adj;
	for(auto ed : G[u]){
		adj = ed.F;
		if(adj == p){
			S.pb({{dpu1[u], dpu2[u]}, {w, adj}});
		} else {
			S.pb({{dp1[adj], dp2[adj]}, {ed.S, adj}});
		}
	}
	ll N = S.size();
	
	pssm[0] = 0;
	for(int i = 1; i <= N; i++) pssm[i] = pssm[i - 1] + max(S[i - 1].F.F, S[i - 1].F.S + S[i - 1].S.F);
	psmx[0] = -Inf;
	for(int i = 1; i <= N; i++) psmx[i] = max(psmx[i - 1] , S[i - 1].F.F + S[i - 1].S.F - max(S[i - 1].F.F, S[i - 1].F.S + S[i - 1].S.F) );
	reverse(all(S));
	for(int i = 0; i <= N; i++) sfsm[i] = pssm[i];
	for(int i = 0; i <= N; i++) sfmx[i] = psmx[i];
	//swap(pssm, sfsm);
	//swap(psmx, sfmx);
	
	pssm[0] = 0;
	for(int i = 1; i <= N; i++) pssm[i] = pssm[i - 1] + max(S[i - 1].F.F, S[i - 1].F.S + S[i - 1].S.F);
	psmx[0] = -Inf;
	for(int i = 1; i <= N; i++) psmx[i] = max(psmx[i - 1] , S[i - 1].F.F + S[i - 1].S.F - max(S[i - 1].F.F, S[i - 1].F.S + S[i - 1].S.F) );
	//if(u == 3) cerr << 
	ans = max(pssm[N], ans);
	
	for(int i = 0; i < N; i++){
		adj = S[i].S.S;
		if(adj == p) continue;
		dpu1[adj] = pssm[i] + sfsm[N - 1 - i];
		dpu2[adj] = dpu1[adj] + max(psmx[i], sfmx[N - 1 - i]);
	}
	
	for(auto ed : G[u]){
		adj = ed.F;
		if(adj != p) dfs(adj, u, ed.S);
	}
}


int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n;
	cin >> n;
	ll u, v, w;
	for(int i = 1; i < n; i++){
		cin >> u >> v >> w;
		G[u].pb({v, w});
		G[v].pb({u, w});
	}
	DFS(1, -1);
	dfs(1, -1, 0);
	cout << ans;
	return 0;
}
/*
5
1 2 10
1 3 40
1 4 15
1 5 20

*/

Compilation message (stderr)

beads.cpp: In function 'll DFS(ll, ll)':
beads.cpp:41:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
beads.cpp: In function 'll dfs(ll, ll, ll)':
beads.cpp:88:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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