Submission #955893

#	Time	Username	Problem	Language	Result	Execution time	Memory
955893		TimAni	Training (IOI07_training)	C++17	Compilation error	0 ms	0 KiB

training

//start-time: 2024-03-31 16:15:50
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1000;
const int K = 10;

class LCA {
private:
    static vector<vector<int>> table;
    static vector<array<int, 2>> par;
    static vector<int> order;
    static vector<int> dep;
    static vector<int> deg;
    int ptr = 0;
public:
    LCA(const vector<vector<int>>& tree){
        int n = tree.size();
        auto dfs = [&](int u, int p, auto&& dfs) -> void {
            for(auto v : tree[u]){
                if(v != p) {
                    table[v][0] = u;
                    dep[v] = dep[u] + 1;
                    par[v] = {u, 1<<(deg[u]++)};
                    dfs(v, u, dfs);
                }
            }
            order[u] = ptr++;
        };
        dfs(0, 0, dfs);
        for(int j = 1; j < K; j++)
            for(int i = 0; i < n; i++)
                table[i][j] = table[table[i][j - 1]][j - 1];
    }
    tuple<int, int> parent(int u){
        return make_tuple(par[u][0], par[u][1]);
    }
    int jump(int u, int dist) {
        for(int i = 0; i < K; i++)
            if(dist & (1<<i))
                u = table[u][i];
        return u;
    }
    int lca(int u, int v){
        if(dep[u] > dep[v]) swap(u, v);
        v = jump(v, dep[v] - dep[u]);
        if(v == u) return v;
        for(int j = K - 1; j >= 0; j--){
            if(table[u][j] != table[v][j]){
                u = table[u][j];
                v = table[v][j];
            }
        }
        return table[u][0];
    }
    int dist(int u, int v){
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }
    int getOrder(int u){
        return order[u];
    }
    void print(){
	    for(int i = 0; i < ptr; i++){
		    cout << dep[i] << ' ';
	    }
    }
};
vector<vector<int>> LCA::table = vector<vector<int>>(N, vector<int>(K));
vector<array<int, 2>> LCA::par = vector<array<int, 2>>(N);
vector<int> LCA::order = vector<int>(N);
vector<int> LCA::dep = vector<int>(N);
vector<int> LCA::deg = vector<int>(N);

void solve(){
    int n, m;
    cin >> n >> m;
    vector<vector<int>> tree(n);
    vector<array<int, 4>> edges;
    ll sum = 0;
    for(int i = 0; i < m; i++){
        int u, v, c;
        cin >> u >> v >> c;
        u--; v--;
        sum += c;
        if(c == 0){
            tree[u].push_back(v);
            tree[v].push_back(u);
        }
        edges.push_back({u, v, c, 0});
    }

    LCA TREE(tree);
    edges.erase(remove_if(edges.begin(), edges.end(), [&](const array<int, 4>& a) {
        return (TREE.dist(a[0], a[1]) % 2 != 0) && a[2];
    }), edges.end());
    
    for(auto &[a, b, c, d] : edges){
        d = TREE.lca(a, b);
    }

    sort(edges.begin(), edges.end(), [&](const array<int, 4>& a, const array<int, 43>& b){
        return TREE.getOrder(a[3]) < TREE.getOrder(b[3]);
    });
    
    int mask1, mask2;
    vector<vector<int>> dp(n, vector<int>(1<<K));
    for(auto &[a, b, w, lca] : edges){
        for(mask1 = 0; a != lca; tie(a, mask1) = TREE.parent(a)) w += dp[a][mask1];
        for(mask2 = 0; b != lca; tie(b, mask2) = TREE.parent(b)) w += dp[b][mask2];

        mask1 |= mask2;

        for(int mask = 0; mask < (1<<K); mask++){
            if(mask & mask1) continue;
            dp[lca][mask] = max(dp[lca][mask], w + dp[lca][mask | mask1]);
        }
    }
    cout << sum - dp[0][0];
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int T = 1;
    //cin >> T;
    while(T--) solve();
    return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 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 training.cpp:2:
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<std::array<int, 4>*, std::vector<std::array<int, 4> > >; _Iterator2 = __gnu_cxx::__normal_iterator<std::array<int, 4>*, std::vector<std::array<int, 4> > >; _Compare = solve()::<lambda(const std::array<int, 4>&, const std::array<int, 43>&)>]':
/usr/include/c++/10/bits/stl_algo.h:82:17:   required from 'void std::__move_median_to_first(_Iterator, _Iterator, _Iterator, _Iterator, _Compare) [with _Iterator = __gnu_cxx::__normal_iterator<std::array<int, 4>*, std::vector<std::array<int, 4> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<solve()::<lambda(const std::array<int, 4>&, const std::array<int, 43>&)> >]'
/usr/include/c++/10/bits/stl_algo.h:1924:34:   required from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<int, 4>*, std::vector<std::array<int, 4> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<solve()::<lambda(const std::array<int, 4>&, const std::array<int, 43>&)> >]'
/usr/include/c++/10/bits/stl_algo.h:1958:38:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<int, 4>*, std::vector<std::array<int, 4> > >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<solve()::<lambda(const std::array<int, 4>&, const std::array<int, 43>&)> >]'
/usr/include/c++/10/bits/stl_algo.h:1974:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<int, 4>*, std::vector<std::array<int, 4> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<solve()::<lambda(const std::array<int, 4>&, const std::array<int, 43>&)> >]'
/usr/include/c++/10/bits/stl_algo.h:4892:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<std::array<int, 4>*, std::vector<std::array<int, 4> > >; _Compare = solve()::<lambda(const std::array<int, 4>&, const std::array<int, 43>&)>]'
training.cpp:105:6:   required from here
/usr/include/c++/10/bits/predefined_ops.h:156:30: error: no match for call to '(solve()::<lambda(const std::array<int, 4>&, const std::array<int, 43>&)>) (std::array<int, 4>&, std::array<int, 4>&)'
  156 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~~~
training.cpp:103:38: note: candidate: 'solve()::<lambda(const std::array<int, 4>&, const std::array<int, 43>&)>'
  103 |     sort(edges.begin(), edges.end(), [&](const array<int, 4>& a, const array<int, 43>& b){
      |                                      ^
training.cpp:103:38: note:   no known conversion for argument 2 from 'std::array<int, 4>' to 'const std::array<int, 43>&'
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 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 training.cpp:2:
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_comp_iter<_Compare>::operator()(_Value&, _Iterator) [with _Value = std::array<int, 4>; _Iterator = __gnu_cxx::__normal_iterator<std::array<int, 4>*, std::vector<std::array<int, 4> > >; _Compare = solve()::<lambda(const std::array<int, 4>&, const std::array<int, 43>&)>]':
/usr/include/c++/10/bits/stl_algo.h:1826:20:   required from 'void std::__unguarded_linear_insert(_RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<int, 4>*, std::vector<std::array<int, 4> > >; _Compare = __gnu_cxx::__ops::_Val_comp_iter<solve()::<lambda(const std::array<int, 4>&, const std::array<int, 43>&)> >]'
/usr/include/c++/10/bits/stl_algo.h:1854:36:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<int, 4>*, std::vector<std::array<int, 4> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<solve()::<lambda(const std::array<int, 4>&, const std::array<int, 43>&)> >]'
/usr/include/c++/10/bits/stl_algo.h:1886:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<int, 4>*, std::vector<std::array<int, 4> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<solve()::<lambda(const std::array<int, 4>&, const std::array<int, 43>&)> >]'
/usr/include/c++/10/bits/stl_algo.h:1977:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<int, 4>*, std::vector<std::array<int, 4> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<solve()::<lambda(const std::array<int, 4>&, const std::array<int, 43>&)> >]'
/usr/include/c++/10/bits/stl_algo.h:4892:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<std::array<int, 4>*, std::vector<std::array<int, 4> > >; _Compare = solve()::<lambda(const std::array<int, 4>&, const std::array<int, 43>&)>]'
training.cpp:105:6:   required from here
/usr/include/c++/10/bits/predefined_ops.h:238:23: error: no match for call to '(solve()::<lambda(const std::array<int, 4>&, const std::array<int, 43>&)>) (std::array<int, 4>&, std::array<int, 4>&)'
  238 |  { return bool(_M_comp(__val, *__it)); }
      |                ~~~~~~~^~~~~~~~~~~~~~
training.cpp:103:38: note: candidate: 'solve()::<lambda(const std::array<int, 4>&, const std::array<int, 43>&)>'
  103 |     sort(edges.begin(), edges.end(), [&](const array<int, 4>& a, const array<int, 43>& b){
      |                                      ^
training.cpp:103:38: note:   no known conversion for argument 2 from 'std::array<int, 4>' to 'const std::array<int, 43>&'
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 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 training.cpp:2:
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = __gnu_cxx::__normal_iterator<std::array<int, 4>*, std::vector<std::array<int, 4> > >; _Value = std::array<int, 4>; _Compare = solve()::<lambda(const std::array<int, 4>&, const std::array<int, 43>&)>]':
/usr/include/c++/10/bits/stl_heap.h:139:48:   required from 'void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<int, 4>*, std::vector<std::array<int, 4> > >; _Distance = long int; _Tp = std::array<int, 4>; _Compare = __gnu_cxx::__ops::_Iter_comp_val<solve()::<lambda(const std::array<int, 4>&, const std::array<int, 43>&)> >]'
/usr/include/c++/10/bits/stl_heap.h:246:23:   required from 'void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<int, 4>*, std::vector<std::array<int, 4> > >; _Distance = long int; _Tp = std::array<int, 4>; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<solve()::<lambda(const std::array<int, 4>&, const std::array<int, 43>&)> >]'
/usr/include/c++/10/bits/stl_heap.h:355:22:   required from 'void std::__make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<int, 4>*, std::vector<std::array<int, 4> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<solve()::<lambda(const std::array<int, 4>&, const std::array<int, 43>&)> >]'
/usr/include/c++/10/bits/stl_algo.h:1666:23:   required from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<int, 4>*, std::vector<std::array<int, 4> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<solve()::<lambda(const std::array<int, 4>&, const std::array<int, 43>&)> >]'
/usr/include/c++/10/bits/stl_algo.h:1937:25:   required from 'void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<int, 4>*, std::vector<std::array<int, 4> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<solve()::<lambda(const std::array<int, 4>&, const std::array<int, 43>&)> >]'
/usr/include/c++/10/bits/stl_algo.h:1953:27:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<int, 4>*, std::vector<std::array<int, 4> > >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<solve()::<lambda(const std::array<int, 4>&, const std::array<int, 43>&)> >]'
/usr/include/c++/10/bits/stl_algo.h:1974:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<int, 4>*, std::vector<std::array<int, 4> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<solve()::<lambda(const std::array<int, 4>&, const std::array<int, 43>&)> >]'
/usr/include/c++/10/bits/stl_algo.h:4892:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<std::array<int, 4>*, std::vector<std::array<int, 4> > >; _Compare = solve()::<lambda(const std::array<int, 4>&, const std::array<int, 43>&)>]'
training.cpp:105:6:   required from here
/usr/include/c++/10/bits/predefined_ops.h:194:23: error: no match for call to '(solve()::<lambda(const std::array<int, 4>&, const std::array<int, 43>&)>) (std::array<int, 4>&, std::array<int, 4>&)'
  194 |  { return bool(_M_comp(*__it, __val)); }
      |                ~~~~~~~^~~~~~~~~~~~~~
training.cpp:103:38: note: candidate: 'solve()::<lambda(const std::array<int, 4>&, const std::array<int, 43>&)>'
  103 |     sort(edges.begin(), edges.end(), [&](const array<int, 4>& a, const array<int, 43>& b){
      |                                      ^
training.cpp:103:38: note:   no known conversion for argument 2 from 'std::array<int, 4>' to 'const std::array<int, 43>&'