Submission #1362989

#	Time	Username	Problem	Language	Result	Execution time	Memory
1362989		tolbi	Tree Decorations (CCO25_day1problem2)	C++20	Compilation error	0 ms	0 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int H = 3;
typedef array<int,H> Hash;
constexpr Hash MOD = {1000000007, 998244353, 998244853};
int32_t main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int N, M;
  cin >> N >> M;
  vector<Hash> fp(N * 2 + 5);
  fp[0] = {1, 1, 1};
  for (int i = 1; i < fp.size(); ++i) {
    for (int j = 0; j < H; ++j) {
      fp[i][j] = fp[i-1][j] * 2;
      if (fp[i][j] >= MOD[j]) fp[i][j] -= MOD[j];
    }
  }
  vector<vector<int>> tree(N);
  for (int i = 0; i < N - 1; ++i) {
    int u, v;
    cin >> u >> v;
    tree[u-1].push_back(v-1);
    tree[v-1].push_back(u-1);
  }
  vector<Hash> hash(N);
  vector<int> red(N), subsz(N, 1), par(N, -1);
  auto dfs = [&](int node, int lnode, auto&&dfs)->void{
    par[node] = lnode;
    vector<pair<Hash, int>> c;
    for (auto it : tree[node]) if (it != lnode) {
      dfs(it, node, dfs);
      c.push_back({hash[it], subsz[it]});
      subsz[node] += subsz[it];
      red[node] += red[it];
    }
    red[node] += subsz[node];
    sort(c.begin(), c.end());
    c.push_back({{1, 1, 1}, 1});
    int pref = 1;
    for (auto &[hsh, sz] : c) {
      for (int i = 0; i < H; ++i) {
        hash[node][i] += (hsh[i] * fp[pref][i])%MOD;
        if (hash[node][i] >= MOD[i]) hash[node][i] -= MOD[i];
      }
      pref += sz * 2;
    }
  };
  dfs(0, -1, dfs);
  map<Hash, int> mp;
  for (int i = 0; i < N; ++i) {
    mp[hash[i]]++;
  }
  set<Hash> ans;
  for (int nd = 0; nd < N; ++nd) {
    if (red[nd] + M == N) {
      map<Hash, int> t;
      queue<array<int,3>> q;
      q.push({nd, par[nd], 1});
      while (q.size()) {
        int node = q.front()[0];
        int lnode = q.front()[1];
        int w = q.front()[2];
        q.pop();
        t[hash[node]] += w;
        for (auto it : tree[node]) if (it != lnode) {
          q.push({it, node, w + 1});
        }
      }
      for (auto [h, k] : t) {
        if (mp[h] < k) {
          goto mahmut;
        }
      }
      ans.insert(hash[nd]);
      mahmut:;
    }
  }
  cout << ans.size() << '\n';
}

Compilation message (stderr)

Main.cpp: In lambda function:
Main.cpp:44:48: error: no match for 'operator%' (operand types are 'std::array<long long int, 3>::value_type' {aka 'long long int'} and 'const Hash' {aka 'const std::array<long long int, 3>'})
   44 |         hash[node][i] += (hsh[i] * fp[pref][i])%MOD;
      |                          ~~~~~~~~~~~~~~~~~~~~~~^~~~
      |                                  |              |
      |                                  |              const Hash {aka const std::array<long long int, 3>}
      |                                  std::array<long long int, 3>::value_type {aka long long int}
In file included from /usr/include/c++/13/valarray:605,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:166,
                 from Main.cpp:1:
/usr/include/c++/13/bits/valarray_after.h:409:5: note: candidate: 'template<class _Dom1, class _Dom2> std::_Expr<std::__detail::_BinClos<std::__modulus, std::_Expr, std::_Expr, _Dom1, _Dom2>, typename std::__fun<std::__modulus, typename _Dom1::value_type>::result_type> std::operator%(const _Expr<_Dom1, typename _Dom1::value_type>&, const _Expr<_Dom2, typename _Dom2::value_type>&)'
  409 |     _DEFINE_EXPR_BINARY_OPERATOR(%, struct std::__modulus)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/valarray_after.h:409:5: note:   template argument deduction/substitution failed:
Main.cpp:44:49: note:   mismatched types 'const std::_Expr<_Dom1, typename _Dom1::value_type>' and 'std::array<long long int, 3>::value_type' {aka 'long long int'}
   44 |         hash[node][i] += (hsh[i] * fp[pref][i])%MOD;
      |                                                 ^~~
/usr/include/c++/13/bits/valarray_after.h:409:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__modulus, std::_Expr, std::_Constant, _Dom, typename _Dom::value_type>, typename std::__fun<std::__modulus, typename _Dom1::value_type>::result_type> std::operator%(const _Expr<_Dom1, typename _Dom1::value_type>&, const typename _Dom::value_type&)'
  409 |     _DEFINE_EXPR_BINARY_OPERATOR(%, struct std::__modulus)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/valarray_after.h:409:5: note:   template argument deduction/substitution failed:
Main.cpp:44:49: note:   mismatched types 'const std::_Expr<_Dom1, typename _Dom1::value_type>' and 'std::array<long long int, 3>::value_type' {aka 'long long int'}
   44 |         hash[node][i] += (hsh[i] * fp[pref][i])%MOD;
      |                                                 ^~~
/usr/include/c++/13/bits/valarray_after.h:409:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__modulus, std::_Constant, std::_Expr, typename _Dom::value_type, _Dom>, typename std::__fun<std::__modulus, typename _Dom1::value_type>::result_type> std::operator%(const typename _Dom::value_type&, const _Expr<_Dom1, typename _Dom1::value_type>&)'
  409 |     _DEFINE_EXPR_BINARY_OPERATOR(%, struct std::__modulus)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/valarray_after.h:409:5: note:   template argument deduction/substitution failed:
Main.cpp:44:49: note:   'const Hash' {aka 'const std::array<long long int, 3>'} is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
   44 |         hash[node][i] += (hsh[i] * fp[pref][i])%MOD;
      |                                                 ^~~
/usr/include/c++/13/bits/valarray_after.h:409:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__modulus, std::_Expr, std::_ValArray, _Dom, typename _Dom::value_type>, typename std::__fun<std::__modulus, typename _Dom1::value_type>::result_type> std::operator%(const _Expr<_Dom1, typename _Dom1::value_type>&, const valarray<typename _Dom::value_type>&)'
  409 |     _DEFINE_EXPR_BINARY_OPERATOR(%, struct std::__modulus)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/valarray_after.h:409:5: note:   template argument deduction/substitution failed:
Main.cpp:44:49: note:   mismatched types 'const std::_Expr<_Dom1, typename _Dom1::value_type>' and 'std::array<long long int, 3>::value_type' {aka 'long long int'}
   44 |         hash[node][i] += (hsh[i] * fp[pref][i])%MOD;
      |                                                 ^~~
/usr/include/c++/13/bits/valarray_after.h:409:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__modulus, std::_ValArray, std::_Expr, typename _Dom::value_type, _Dom>, typename std::__fun<std::__modulus, typename _Dom1::value_type>::result_type> std::operator%(const valarray<typename _Dom::value_type>&, const _Expr<_Dom1, typename _Dom1::value_type>&)'
  409 |     _DEFINE_EXPR_BINARY_OPERATOR(%, struct std::__modulus)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/valarray_after.h:409:5: note:   template argument deduction/substitution failed:
Main.cpp:44:49: note:   'const Hash' {aka 'const std::array<long long int, 3>'} is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
   44 |         hash[node][i] += (hsh[i] * fp[pref][i])%MOD;
      |                                                 ^~~
/usr/include/c++/13/valarray:1200:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__modulus, std::_ValArray, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__modulus, _Tp>::result_type> std::operator%(const valarray<_Tp>&, const valarray<_Tp>&)'
 1200 | _DEFINE_BINARY_OPERATOR(%, __modulus)
      | ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/valarray:1200:1: note:   template argument deduction/substitution failed:
Main.cpp:44:49: note:   mismatched types 'const std::valarray<_Tp>' and 'std::array<long long int, 3>::value_type' {aka 'long long int'}
   44 |         hash[node][i] += (hsh[i] * fp[pref][i])%MOD;
      |                                                 ^~~
/usr/include/c++/13/valarray:1200:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__modulus, std::_ValArray, std::_Constant, _Tp, _Tp>, typename std::__fun<std::__modulus, _Tp>::result_type> std::operator%(const valarray<_Tp>&, const typename valarray<_Tp>::value_type&)'
 1200 | _DEFINE_BINARY_OPERATOR(%, __modulus)
      | ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/valarray:1200:1: note:   template argument deduction/substitution failed:
Main.cpp:44:49: note:   mismatched types 'const std::valarray<_Tp>' and 'std::array<long long int, 3>::value_type' {aka 'long long int'}
   44 |         hash[node][i] += (hsh[i] * fp[pref][i])%MOD;
      |                                                 ^~~
/usr/include/c++/13/valarray:1200:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__modulus, std::_Constant, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__modulus, _Tp>::result_type> std::operator%(const typename valarray<_Tp>::value_type&, const valarray<_Tp>&)'
 1200 | _DEFINE_BINARY_OPERATOR(%, __modulus)
      | ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/valarray:1200:1: note:   template argument deduction/substitution failed:
Main.cpp:44:49: note:   'const Hash' {aka 'const std::array<long long int, 3>'} is not derived from 'const std::valarray<_Tp>'
   44 |         hash[node][i] += (hsh[i] * fp[pref][i])%MOD;
      |                                                 ^~~