Submission #924956

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

beads

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200200;
const ll INF = 5e17;
vector<pair<int, int>> adj[N];
ll dp[4][N];
void dfs(int v, int p = -1) {
    ll mx1 = -INF, mx2 = -INF;
    ll mx[3] = { -INF, -INF, -INF };
    for (auto& [x, w] : adj[v]) {
        if (x == p) continue;
        dfs(x, v);
        ll val = max({ dp[0][x], dp[1][x] + w });
        // 0
        dp[0][v] += max({ dp[0][x], dp[1][x] + w, dp[2][x] + w, dp[3][x] });
        // 1 , 2
        dp[1][v] += val;
        mx1 = max(mx1, dp[0][x] + w - val);
        dp[2][v] += val;
        mx2 = max(mx2, max({ dp[0][x] , dp[3][x] }) + w - val);
        // 3
        dp[3][v] += val;
        mx[1] = max(mx[1], dp[0][x] + w - val);
        if (mx[0] < mx[1]) swap(mx[0], mx[1]);
        mx[2] = max(mx[2], dp[3][x] + w - val);
    }
    dp[1][v] += mx1;
    dp[2][v] += mx2;
    dp[3][v] += max(mx[0] + mx[1], mx[0] + mx[2]);
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 1;i < n;i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({ v, w });
        adj[v].push_back({ u, w });
    }
    dfs(1);
    cout << max(dp[0][1], dp[3][1]);
    return 0;
}

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