Submission #735207

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
735207	2023-05-03T17:29:11 Z	vjudge1	Beads and wires (APIO14_beads)	C++17	Compilation error	0 ms	0 KB

beads

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

#define int int64_t

int main() {
        int n;
        cin >> n;
        if (n <= 2) return cout << 0, 0;
        vector<vector<pair<int, int>>> adj(n);
        for (int i = 0; i < n - 1; i++) {
                int a, b, c;
                cin >> a >> b >> c;
                a--, b--;
                adj[a].emplace_back(b, c);
                adj[b].emplace_back(a, c);
        }
        vector<vector<int>> f(2, vector<int>(n, 0));
        function<void(int, int)> dfs = [&](int u, int p) {
                f[1][u] = -1e10;
                f[0][u] = 0;
                for (pair<int, int>& e : adj[u]) {
                        int v = e.first;
                        int c = e.second;
                        if (v == p) continue;
                        dfs(v, u);
                        f[0][u] += max(f[0][v], f[1][v] + c);
                }
                for (pair<int, int>& e : adj[u]) {
                        int v = e.first;
                        int c = e.second;
                        if (v == p) continue;
                        f[1][u] = max(f[1][u], f[0][u] - max(f[0][v], f[1][v] + c) + f[0][v] + c);
                }
        };

        int res = 0;

        function<void(int, int)> reroot = [&](int u, int p) {
                // re-calc f[u]
                int ff0 = f[0][u];
                int ff1 = f[1][u];
                f[0][u] = 0;
                for (pair<int, int>& e : adj[u]) {
                        int v = e.first, c = e.second;
                        f[0][u] += max(f[0][v], f[1][v] + c);
                }
                vector<int> bestf(2, -1e10);
                for (pair<int, int>& e : adj[u]) {
                        int v = e.first, c = e.second;
                        bestf.emplace_back(f[0][u] - max(f[0][v], f[1][v] + c) + f[0][v] + c);
                        int i = bestf.size() - 1;
                        while (i > 0 && bestf[i] > bestf[i - 1]) swap(bestf[i], bestf[i - 1]), i--;
                        bestf.pop_back();
                }
                f[1][u] = bestf[0];
                // update result
                vector<int> best;
                for (pair<int, int>& e : adj[u]) {
                        int v = e.first, c = e.second;
                        best.emplace_back(f[0][v] + c - max(f[0][v], f[1][v] + c));
                        int i = best.size() - 1;
                        while (i > 0 && best[i] > best[i - 1]) swap(best[i], best[i - 1]), i--;
                        if (best.size() > 2) best.pop_back();
                }
                if (best.size() == 2) res = max(res, f[0][u] + max(0, best[0] + best[1]));
                // move to the next one

                for (pair<int, int>& e : adj[u]) {
                        int v = e.first, c = e.second;
                        if (v == p) continue;
                        int f0 = f[0][u];
                        f[0][u] -= max(f[0][v], f[1][v] + c);
                        f[1][u] = bestf[0] == (f[0][u] + f[0][v] + c) ? bestf[1] : bestf[0];
                        f[1][u] -= max(f[0][v], f[1][v] + c);
                        reroot(v, u);
                        f[1][u] = bestf[0];
                        f[0][u] = f0;
                }
                f[0][u] = ff0;
                f[1][u] = ff1;
        };

        dfs(0, -1);
        reroot(0, -1);

        cout << res;
}

Compilation message

beads.cpp:4:13: error: '::main' must return 'int'
    4 | #define int int64_t
      |             ^~~~~~~
beads.cpp:6:1: note: in expansion of macro 'int'
    6 | int main() {
      | ^~~
beads.cpp: In lambda function:
beads.cpp:66:88: error: no matching function for call to 'max(int, __gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type)'
   66 |                 if (best.size() == 2) res = max(res, f[0][u] + max(0, best[0] + best[1]));
      |                                                                                        ^
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:66:88: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type' {aka 'long int'})
   66 |                 if (best.size() == 2) res = max(res, f[0][u] + max(0, best[0] + best[1]));
      |                                                                                        ^
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:66:88: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type' {aka 'long int'})
   66 |                 if (best.size() == 2) res = max(res, f[0][u] + max(0, best[0] + best[1]));
      |                                                                                        ^
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:66:88: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   66 |                 if (best.size() == 2) res = max(res, f[0][u] + max(0, best[0] + best[1]));
      |                                                                                        ^
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:66:88: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   66 |                 if (best.size() == 2) res = max(res, f[0][u] + max(0, best[0] + best[1]));
      |                                                                                        ^