Submission #1129358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129358		Hamed_Ghaffari	Beads and wires (APIO14_beads)	C++20	0 / 100	6 ms	5108 KiB

beads

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

using ll = long long;
using pll = pair<ll, ll>;
using pii = pair<int, int>;

#define SZ(x) int(x.size())
#define pb push_back
#define all(x) x.begin(), x.end()
#define maxs(a, b) (a = max(a,b))
#define mins(a, b) (a = min(a,b))
#define Mp make_pair
#define mid ((l+r)>>1)

const int MXN = 2e5+1;
const int INF = 1e9;

int n;
ll dp[MXN][2];
vector<pii> g[MXN];

void insert(ll &mx1, ll &mx2, ll &mx3, ll x) {
    if(x>=mx1) mx3=mx2, mx2=mx1, mx1=x;
    else if(x>=mx2) mx3=mx2, mx2=x;
    else if(x>=mx3) mx3=x;
}

// ll erase(ll mx1, ll mx2, ll mx3, ll x) {
//     if(x==mx1) return mx2+mx3;
//     if(x==mx2) return mx1+mx3;
//     return mx1+mx2;
// }

void dfs(int v, int p=0) {
    ll sum=0, mx1=-INF, mx2=-INF, mx3=-INF;
    for(auto [u,w]: g[v])
        if(u!=p) {
            dfs(u, v);
            ll val = max(dp[u][0], dp[u][1]+w);
            sum += val;
            insert(mx1, mx2, mx3, dp[u][0]+w-val);
        }
    dp[v][0] = sum + max(0ll, mx1+mx2);
    dp[v][1] = sum + max(mx1, mx1 + mx2 + mx3);
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

    cin >> n;
    for(int i=0,u,v,w; i<n-1; i++) {
        cin >> u >> v >> w;
        g[u].pb(Mp(v,w));
        g[v].pb(Mp(u,w));
    }

    dfs(1);
    cout << dp[1][0] << '\n';

    return 0;
}

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