Submission #754035

#	Time	Username	Problem	Language	Result	Execution time	Memory
754035		thinknoexit	Beads and wires (APIO14_beads)	C++17	0 / 100	4 ms	5032 KiB

beads

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200200;
vector<pair<int, ll>> adj[N];
ll dp[2][N];
void dfs(int v, int p = 0) {
    ll mx = -4e10, mx2 = -4e10;
    ll sum = 0;
    for (auto& [x, w] : adj[v]) {
        if (x == p) continue;
        dfs(x, v);
        ll val = max(dp[0][x], dp[1][x] + w);
        sum += val;
        ll val2 = dp[0][x] + w - val;
        if (val2 > mx) {
            mx2 = mx;
            mx = val2;
        }
        else if (val2 > mx2) {
            mx2 = val2;
        }
    }
    dp[1][v] = sum + mx;
    dp[0][v] = max(sum, sum + mx + mx2);
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 1;i < n;i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        adj[u].push_back({ v,w });
        adj[v].push_back({ u,w });
    }
    int s;
    for (int i = 1;i <= n;i++) {
        if (adj[i].size() == 1) {
            s = i;
            break;
        }
    }
    dfs(s);
    cout << dp[0][s];
    return 0;
}
/*
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
*/

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:46:20: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
   46 |     cout << dp[0][s];
      |                    ^

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