Submission #702700

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

beads

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

#define N 200000

vector<pair<unsigned, int64_t>> g[N];
int64_t dp1[N], dp2[N]; // Use or don't use the parent edge.

void calc_dp(unsigned u, unsigned parent, int64_t parent_edge_w)
{
    int64_t diff_max1 = INT64_MIN, diff_max2 = INT64_MIN;

    for (auto const &[v, w] : g[u])
    {
        if (v != parent)
        {
            calc_dp(v, u, w);
            dp1[u] += dp1[v];
            dp2[u] += dp1[v];
            if (dp2[v] + w - dp1[v] >= diff_max1)
            {
                diff_max2 = diff_max1;
                diff_max1 = dp2[v] + w - dp1[v];
            }
            else if (dp2[v] + w - dp1[v] > diff_max2)
            {
                diff_max2 = dp2[v] + w - dp1[v];
            }
        }
    }

    if (diff_max1 != INT64_MIN)
        dp1[u] += max<int64_t>(parent_edge_w + diff_max1, 0);
    if (diff_max2 != INT64_MIN)
        dp2[u] += max<int64_t>(diff_max1 + diff_max2, 0);
    dp1[u] = max(dp1[u], dp2[u]);
}

int main()
{
    size_t n;
    scanf("%zu", &n);

    for (size_t i = 0; i < n - 1; i++)
    {
        unsigned u, v, w;
        cin >> u >> v >> w;
        g[u - 1].emplace_back(v - 1, w);
        g[v - 1].emplace_back(u - 1, w);
    }

    calc_dp(0, -1, 0);
    printf("%" PRId64 "\n", dp2[0]);
}

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     scanf("%zu", &n);
      |     ~~~~~^~~~~~~~~~~

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