Submission #924986

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

beads

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200200;
const ll INF = 2e9;
vector<pair<int, int>> adj[N];
ll dp[5][N];
void dfs(int v, int p = -1) {
    ll mx0 = 0, mx2 = -INF, mx3 = -INF;
    pair<ll, int> mxf[3] = { {-INF,0}, {-INF,0}, {-INF,0} };
    pair<ll, int> mxs[3] = { {-INF,0}, {-INF,0}, {-INF,0} };
    for (auto& [x, w] : adj[v]) {
        if (x == p) continue;
        dfs(x, v);
        ll val = max(dp[1][x], dp[2][x] + w);
        // 0
        dp[0][v] += val;
        mx0 = max(mx0, max(dp[0][x], dp[3][x] + w) - val);
        // 1
        dp[1][v] += val;
        // 2
        dp[2][v] += val;
        mx2 = max(mx2, dp[1][x] + w - val);
        // 3
        dp[3][v] += val;
        mx3 = max(mx3, dp[4][x] + w - val);
        // 4
        dp[4][v] += val;
        mxs[0] = max(mxs[0], { dp[1][x] + w - val, x });
        mxs[1] = max(mxs[1], { dp[0][x] + w - val, x });
        mxs[2] = max(mxs[2], { dp[4][x] + w - val, x });
        if (mxf[0] < mxs[0]) swap(mxf[0], mxs[0]);
        if (mxf[1] < mxs[1]) swap(mxf[1], mxs[1]);
        if (mxf[2] < mxs[2]) swap(mxf[2], mxs[2]);
    }
    dp[0][v] += mx0;
    dp[2][v] += mx2;
    dp[3][v] += mx3;
    ll res = 0;
    if (mxf[0].second != mxf[1].second) res = max(res, mxf[0].first + mxf[1].first);
    else res = max({ res, mxf[0].first + mxs[1].first, mxs[0].first + mxf[1].first });
    if (mxf[0].second != mxf[2].second) res = max(res, mxf[0].first + mxf[2].first);
    else res = max({ res, mxf[0].first + mxs[2].first, mxs[0].first + mxf[2].first });
    dp[4][v] += res;
}
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[4][1]);
    return 0;
}

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