Submission #702699

#	Time	Username	Problem	Language	Result	Execution time	Memory
702699		finn__	Beads and wires (APIO14_beads)	C++17	Compilation error	0 ms	0 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(parent_edge_w + diff_max1, 0);
    if (diff_max2 != INT64_MIN)
        dp2[u] += max(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 'void calc_dp(unsigned int, unsigned int, int64_t)':
beads.cpp:33:51: error: no matching function for call to 'max(int64_t, int)'
   33 |         dp1[u] += max(parent_edge_w + diff_max1, 0);
      |                                                   ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from beads.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
beads.cpp:33:51: note:   deduced conflicting types for parameter 'const _Tp' ('long int' and 'int')
   33 |         dp1[u] += max(parent_edge_w + diff_max1, 0);
      |                                                   ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from beads.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
beads.cpp:33:51: note:   deduced conflicting types for parameter 'const _Tp' ('long int' and 'int')
   33 |         dp1[u] += max(parent_edge_w + diff_max1, 0);
      |                                                   ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from beads.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
beads.cpp:33:51: note:   mismatched types 'std::initializer_list<_Tp>' and 'long int'
   33 |         dp1[u] += max(parent_edge_w + diff_max1, 0);
      |                                                   ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from beads.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
beads.cpp:33:51: note:   mismatched types 'std::initializer_list<_Tp>' and 'long int'
   33 |         dp1[u] += max(parent_edge_w + diff_max1, 0);
      |                                                   ^
beads.cpp:35:47: error: no matching function for call to 'max(int64_t, int)'
   35 |         dp2[u] += max(diff_max1 + diff_max2, 0);
      |                                               ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from beads.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
beads.cpp:35:47: note:   deduced conflicting types for parameter 'const _Tp' ('long int' and 'int')
   35 |         dp2[u] += max(diff_max1 + diff_max2, 0);
      |                                               ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from beads.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
beads.cpp:35:47: note:   deduced conflicting types for parameter 'const _Tp' ('long int' and 'int')
   35 |         dp2[u] += max(diff_max1 + diff_max2, 0);
      |                                               ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from beads.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
beads.cpp:35:47: note:   mismatched types 'std::initializer_list<_Tp>' and 'long int'
   35 |         dp2[u] += max(diff_max1 + diff_max2, 0);
      |                                               ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from beads.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
beads.cpp:35:47: note:   mismatched types 'std::initializer_list<_Tp>' and 'long int'
   35 |         dp2[u] += max(diff_max1 + diff_max2, 0);
      |                                               ^
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);
      |     ~~~~~^~~~~~~~~~~