Submission #734253

#	Time	Username	Problem	Language	Result	Execution time	Memory
734253		Alihan_8	Beads and wires (APIO14_beads)	C++17	0 / 100	1 ms	320 KiB

beads

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define pb push_back
#define ln '\n'
#define int long long

template <class _T>
bool chmin(_T &x, const _T &y){
    bool flag = false;
    if ( x > y ){
        x = y; flag |= true;
    }
    return flag;
}

template <class _T>
bool chmax(_T &x, const _T &y){
    bool flag = false;
    if ( x < y ){
        x = y; flag |= true;
    }
    return flag;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    vector <pair<int,int>> g[n];
    for ( int i = 1; i < n; i++ ){
        int x, y, w; cin >> x >> y >> w;
        g[--x].pb({--y, w});
        g[y].pb({x, w});
    }
    vector <array<int,2>> dp(n);
    const int inf = 1e15 + 1;
    function <void(int,int,int)> dfs = [&](int x, int par, int prev){
        int cnt = 0, l = -inf, r = -inf;
        for ( auto [to, w]: g[x] ){
            if ( to == par ) continue;
            dfs(to, x, w);
            cnt += dp[to][1];
            int v = dp[to][0] - dp[to][1] + w;
            if ( l <= v ){
                r = l; l = v;
            }
            else chmax(r, v);
        }
        if ( r != -inf ){
            chmax(dp[x][0], cnt + l + r);
        }
        chmax(dp[x][0], cnt);
        for ( auto [to, w]: g[x] ){
            if ( to == par ) continue;
            chmax(dp[x][1], cnt - dp[to][1] + dp[to][0] + w + prev);
        }

        chmax(dp[x][1], dp[x][0]);
    };
    dfs(0, 0, 0);
    cout << dp[0][0];

    cout << '\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
*/

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