Submission #84285

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

beads

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 2e5 + 5;

int up[Nmax], dp[Nmax][2], best[Nmax];
vector<int> v[Nmax], c[Nmax];
int x, y, n, i, cost;


void dfs(int node, int dad = 0)
{
    int i;

    for(i=0; i<v[node].size(); ++i)
        if(v[node][i] != dad)
        {
            up[v[node][i]] = c[node][i];
            dfs(v[node][i], node);
        }

    int add1 = -1e9, add2 = -1e9, sum = 0;

    for(auto son : v[node])
        if(son != dad)
        {
            sum += best[son];
            int curr = up[son] - best[son] + dp[son][0];
            if(curr >= add1) add2 = add1, add1 = curr;
                else if(curr > add2) add2 = curr;
        }

    dp[node][0] = max(sum, sum + add1 + add2);
    dp[node][1] = add1 + sum + up[node];

    best[node] = max(dp[node][0], dp[node][1]);
}

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

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

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

    return 0;
}

Compilation message (stderr)

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

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