Submission #494900

#	Time	Username	Problem	Language	Result	Execution time	Memory
494900		Stickfish	Beads and wires (APIO14_beads)	C++17	28 / 100	1066 ms	5528 KiB

beads

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 2e5 + 123;
const int INF = 1.77013e9;
vector<pair<int, int>> edg[MAXN];
int dp[MAXN][2];

void get_ans(int v, int rt) {
    dp[v][0] = dp[v][1] = 0;
    if (rt == -1) {
        int w0 = -INF;
        int w1 = -INF;
        for (auto [u, w] : edg[v]) {
            get_ans(u, v);
            dp[v][0] += max(dp[u][1], dp[u][0]);
            int bonus = w + min(0, dp[u][0] - dp[u][1]);
            if (bonus > w0) {
                w1 = w0;
                w0 = bonus;
            } else if (bonus > w1) {
                w1 = bonus;
            }
        }
        if (w0 + w1 > 0) {
            dp[v][0] = w0 + w1;
        }
    } else {
        int rtw;
        for (auto [u, w] : edg[v]) {
            if (u == rt) {
                rtw = w;
                continue;
            }
            get_ans(u, v);
            dp[v][0] += max(dp[u][0], dp[u][1]);
        }
        dp[v][1] = dp[v][0];
        for (auto [u, w] : edg[v]) {
            if (u == rt)
                continue;
            dp[v][1] = max(dp[v][1], dp[v][0] + rtw + w + min(0, dp[u][0] - dp[u][1]));
        }
    }
}

signed main() {
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int u, v, d;
        cin >> u >> v >> d;
        --u, --v;
        edg[u].push_back({v, d});
        edg[v].push_back({u, d});
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        get_ans(i, -1);
        ans = max(ans, dp[i][0]);
    }
    cout << ans << endl;
}

Compilation message (stderr)

beads.cpp: In function 'void get_ans(int, int)':
beads.cpp:43:47: warning: 'rtw' may be used uninitialized in this function [-Wmaybe-uninitialized]
   43 |             dp[v][1] = max(dp[v][1], dp[v][0] + rtw + w + min(0, dp[u][0] - dp[u][1]));
      |                                      ~~~~~~~~~^~~~~

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