Submission #1109803

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109803		Sharky	Beads and wires (APIO14_beads)	C++17	100 / 100	110 ms	33720 KiB

beads

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 2e5 + 10;
const int inf = 1e13;

int n, dp[N][2][2];
vector<pair<int, int>> adj[N];

void dfs(int u, int p) {
    dp[u][0][1] = dp[u][1][0] = dp[u][1][1] = -inf;
    vector<pair<int, int>> vec;
    int non_root = 0;
    for (auto& [v, w] : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        non_root++;
        dp[u][0][0] += max(dp[v][0][1] + w, dp[v][0][0]);
        vec.push_back({dp[v][0][0] + w - max(dp[v][0][1] + w, dp[v][0][0]), v});
    }
    if (non_root == 0) return;
    int sum = dp[u][0][0];
    sort(vec.begin(), vec.end(), [] (auto a, auto b) { return a.first > b.first; });
    dp[u][0][1] = dp[u][0][0] + vec[0].first;
    for (auto& [v, w] : adj[u]) {
        if (v == p) continue;
        dp[u][1][1] = max(dp[u][1][1], sum + max(dp[v][0][0], dp[v][1][0]) + w - max(dp[v][0][0], dp[v][0][1] + w));
        dp[u][1][0] = max(dp[u][1][0], sum + max(dp[v][1][0], dp[v][1][1] + w) - max(dp[v][0][0], dp[v][0][1] + w));
        if (vec[0].second != v) dp[u][1][0] = max(dp[u][1][0], sum + max(dp[v][1][0], dp[v][0][0]) + w - max(dp[v][0][0], dp[v][0][1] + w) + vec[0].first);
        else if (vec.size() > 1) dp[u][1][0] = max(dp[u][1][0], sum + max(dp[v][1][0], dp[v][0][0]) + w - max(dp[v][0][0], dp[v][0][1] + w) + vec[1].first);
    }
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    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, -1);
    cout << max(dp[1][0][0], dp[1][1][0]) << '\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: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 29 / 29
• Subtask 4: 43 / 43