Submission #115417

#	Time	Username	Problem	Language	Result	Execution time	Memory
115417		zubec	Beads and wires (APIO14_beads)	C++14	100 / 100	201 ms	23408 KiB

beads

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

const int N = 200100;

vector <pair<int, int> > g[N];

ll dp[4][N];

int n;

void dfs(int v, int p, int lenTo){

    ll sum = 0;

    ll mx1 = -1e15, mx2 = -1e15, mx3 = -1e15;

    for (int i = 0; i < g[v].size(); i++){
        int to = g[v][i].first, len = g[v][i].second;
        if (to == p)
            continue;
        dfs(to, v, len);
        sum += max(dp[0][to], dp[1][to]);

        mx1 = max(mx1, max(dp[2][to], dp[3][to]) - max(dp[0][to], dp[1][to]));

        mx2 = max(mx2, dp[0][to] + len - max(dp[0][to], dp[1][to]));
        mx3 = max(mx3, dp[2][to] + len - max(dp[0][to], dp[1][to]));

    }

    dp[0][v] = max(0ll, sum);
    dp[2][v] = max(0ll, sum + mx1);

    if (v != 1){
        dp[1][v] = max(0ll, sum + mx2 + lenTo);
        dp[3][v] = max(0ll, sum + mx3 + lenTo);
    }

    mx1 = mx2 = -1e15;
    for (int i = 0; i < g[v].size(); i++){
        int to = g[v][i].first, len = g[v][i].second;
        if (to == p)
            continue;

        dp[2][v] = max(dp[2][v], sum + mx1 + max(dp[0][to], dp[2][to]) + len - max(dp[0][to], dp[1][to]) );
        dp[2][v] = max(dp[2][v], sum + mx2 + dp[0][to] + len - max(dp[0][to], dp[1][to]));

        mx1 = max(mx1, dp[0][to] + len - max(dp[0][to], dp[1][to]));
        mx2 = max(mx2, dp[2][to] + len - max(dp[0][to], dp[1][to]));

    }


}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin >> n;
    for (int i = 2; i <= n; i++){
        int u, v, c;
        cin >> u >> v >> c;
        g[u].push_back({v, c});
        g[v].push_back({u, c});
    }

    dfs(1, 0, 0);

    cout << max({dp[0][1], dp[1][1], dp[2][1], dp[3][1]});

}

/**



*/

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int, int)':
beads.cpp:20:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++){
                     ~~^~~~~~~~~~~~~
beads.cpp:43:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++){
                     ~~^~~~~~~~~~~~~

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