oj.uz

Submission #702688

# Submission time Handle Problem Language Result Execution time Memory
702688 2023-02-24T19:57:35 Z finn__ Beads and wires (APIO14_beads) C++17
0 / 100
 3 ms 5012 KB 
#include <bits/stdc++.h>
using namespace std;

#define N 200000

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

void calc_dp(unsigned u, unsigned parent, int parent_edge_w)
{
    int diff_max1 = INT_MIN, diff_max2 = INT_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 != INT_MIN)
        dp1[u] += parent_edge_w + diff_max1;
    if (diff_max2 != INT_MIN)
        dp2[u] += diff_max1 + diff_max2;
}

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("%d\n", dp2[0]);
}

Compilation message

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

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5012 KB Output is correct
2 Correct 3 ms 5012 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 3 ms 4980 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5012 KB Output is correct
2 Correct 3 ms 5012 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 3 ms 4980 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5012 KB Output is correct
2 Correct 3 ms 5012 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 3 ms 4980 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5012 KB Output is correct
2 Correct 3 ms 5012 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 3 ms 4980 KB Output isn't correct
5 Halted 0 ms 0 KB -