Submission #1129403

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129403		Hamed_Ghaffari	Beads and wires (APIO14_beads)	C++20	13 / 100	4 ms	4936 KiB

beads

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

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

#define X first
#define Y second
#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 dp00[MXN], dp01[MXN], dp10[MXN], dp11[MXN];
vector<pii> g[MXN];

void dfs(int v, int p=0) {
    for(auto [u, w] : g[v])
        if(u != p)
            dfs(u, v);
    
    dp01[v] = dp10[v] = dp11[v] = -INF;
    ll mx1=-INF, mx2=-INF;
    for(auto [u, w] : g[v])
        if(u!=p) {
            ll val = max({dp00[u], dp11[u], dp10[u]+w});
            dp00[v] += val;
            val = max(dp00[u],dp11[u])+w-val;
            if(val>=mx1) mx2=mx1, mx1=val;
            else if(val>=mx2) mx2=val;
        }
    for(auto [u, w] : g[v])
        if(u!=p) {
            ll val = max({dp00[u], dp11[u], dp10[u]+w});
            maxs(dp11[v], dp00[v]-val+dp01[u]+w);
            maxs(dp01[v], dp00[v]-val+max(dp00[u], dp11[u])+w);
            maxs(dp10[v], dp00[v]-val+dp00[u]+w);
            maxs(dp11[v], dp00[v]-val+dp00[u]+w
            + (max(dp00[u], dp11[u])+w-val==mx1 ? mx2 : mx1));
        }
}

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 << max(dp00[1], dp11[1]) << '\n';

    return 0;
}

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