Submission #94601

#	Time	Username	Problem	Language	Result	Execution time	Memory
94601		Alexa2001	Beads and wires (APIO14_beads)	C++17	0 / 100	8 ms	5120 KiB

beads

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 2e5 + 5, inf = 2e9 + 2;
typedef long long ll;

int dp[Nmax][4];
vector< pair<int,int> > v[Nmax];


void dfs(int node, int dad = 0)
{
    vector<int> zero, one, two;
    int up = 0, son, cost, i;

    for(auto it : v[node])
    {
        tie(son, cost) = it;
        if(son != dad)
        {
            dfs(son, node);
            zero.push_back(max(dp[son][0], dp[son][3]));
            one.push_back(dp[son][1]);
            two.push_back(dp[son][2]);
        }
        else up = cost;
    }

    /// case 0

    ll sum = 0;
    for(auto it : zero) sum += it;
    sum = max(sum, (ll)-inf);
    if(sum > dp[node][0]) dp[node][0] = sum;

    /// cases 1 & 2

    ll best = sum, best1 = -inf, best2 = -inf;
    for(i=0; i<zero.size(); ++i)
        best = max(best, sum - zero[i] + one[i]);

    for(i=0; i<zero.size(); ++i)
    {
        ll x = (ll) two[i] - zero[i];
        if(x >= best1) best2 = best1, best1 = x;
            else if(x > best2) best2 = x;
    }

    best = max(best, (ll)-inf);
    best1 = sum + best1 + best2;
    best1 = max(best1, (ll)-inf);

    dp[node][1] = dp[node][2] = max(best, best1);

    /// case 3

    best = -inf;
    for(i=0; i<zero.size(); ++i)
        best = max(best, sum - zero[i] + two[i]);

    dp[node][3] = best;


    ///
    dp[node][2] += up;
    dp[node][3] += up;
}

int main()
{
   // freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    int i, n, x, y, cost;
    cin >> n;
    for(i=1; i<=n; ++i) dp[i][0] = dp[i][1] = dp[i][2] = dp[i][3] = -inf;

    for(i=1; i<n; ++i)
    {
        cin >> x >> y >> cost;
        v[x].push_back({y, cost});
        v[y].push_back({x, cost});
    }

    dfs(1);
    cout << max(dp[1][0], dp[1][1]) << '\n';

    return 0;
}

Compilation message (stderr)

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

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