Submission #1101706

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101706		flyingkite	Beads and wires (APIO14_beads)	C++17	0 / 100	2 ms	3156 KiB

beads

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()

const ll N = 1e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 350;
ll n;
vector<pll>adj[N];
ll dp[N][3]; // 0 la dang ko la mid, 1 la chua la mid va blue-wire wating, 2 la la mid
void dfs(ll u, ll par){
    pll mx = {-inf, -inf};
    dp[u][1] = -inf;
    for(auto x : adj[u]){
        ll v = x.F, w = x.S;
        if(v == par) continue;
        dfs(v, u);
        dp[u][1] = max(dp[u][0] + max(dp[v][0], dp[v][2]) + w, dp[u][1] + max({dp[v][1] + w, dp[v][0], dp[v][2]}));
        dp[u][0] += max({dp[v][0], dp[v][1] + w, dp[v][2]});
        ll cost = -max({dp[v][0], dp[v][1] + w, dp[v][2]}) + max(dp[v][0], dp[v][2]) + w;
        if(cost > mx.F) mx.S = mx.F, mx.F = cost;
        else if(cost > mx.S) mx.S = cost;
    }
    dp[u][2] = dp[u][0] + mx.F + mx.S;
}
void to_thic_cau(){
    cin >> n;
    for(int i = 1; i <= n - 1;i++){
        ll u,v,c; cin >> u >> v >> c;
        adj[u].pb({v,c}); adj[v].pb({u,c});
    }
    dfs(1, 0);
    cout << max(dp[1][0], dp[1][2]) << '\n';
}
/*
10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34
*/
signed main()   
{  
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll tc = 1;
    //cin >> tc;
    while(tc--) to_thic_cau();
}

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