oj.uz

Submission #1068703

# Submission time Handle Problem Language Result Execution time Memory
1068703 2024-08-21T11:25:16 Z beaconmc Digital Circuit (IOI22_circuit) C++17
Compilation error
 0 ms 0 KB 
    #include <bits/stdc++.h>
     
    typedef long long ll;
    using namespace std;
     
     
    #define FOR(i, x, y) for(ll i=x; i<y; i++)
    #define FORNEG(i, x, y) for(ll i=x; i>y; i--)
    #define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)
     
     
    basic_string<ll> edges[200001];
    ll possible[200001];
    ll contrib[200001];
    ll dps[200001];
    basic_string<int> p;
     
     
     
     
    int initdfs(ll a){
      if (edges[a].size() == 0) return possible[a] = 1;
     
      ll temp = 1;
      for (auto&i : edges[a]){
        temp *= initdfs(i);
        temp %= 1000002022;
      }
      temp *= edges[a].size();
      temp %= 1000002022;
     
     
      return possible[a] = temp;
    }
     
    int dp(ll a){
      if (a==0) return 1;
      if (dps[a] != -1) return dps[a];
     
      ll temp = 1;
     
      for (auto&i : edges[p[a]]){
        if (i != a) temp *= possible[i];
        temp %= 1000002022;
      }
      dps[a] = temp * dp(p[a]) % 1000002022;
      return dps[a];
    }
     
    ll n,m;
     
     
     
    const ll NN = (1<<18);
    ll tree[NN*2];
    ll actual[NN*2];
    ll lazy[NN*2];
     
    int actupd(ll a, ll b, ll val, ll k=1, ll x = 0, ll y = NN-1){
     
      if (b<x || a>y) return actual[k];
      if (a<=x && y<=b){
     
        actual[k] += val;
        actual[k] %= 1000002022;
        return actual[k];
      }
      ll mid = (x+y)/2;
     
     
      actual[k] =  actupd(a,b,val,k*2, x, mid) + actupd(a,b,val,k*2+1, mid+1, y);
      actual[k] %= 1000002022;
     
      return actual[k];
    }
     
     
    void prop(ll k){
      lazy[k*2] += lazy[k];
      lazy[k*2+1] += lazy[k];
      if (lazy[k] %2==1){
        tree[k] = (actual[k] - tree[k]+1000002022)%1000002022;
      }
      lazy[k] = 0;
    }
     
     
    int upd(ll a, ll b, ll k=1, ll x = 0, ll y = NN-1){
      if (b<x || a>y) return lazy[k]%2==0 ? tree[k] : ((actual[k] - tree[k]+1000002022)%1000002022);
      if (a<=x && y<=b){
        lazy[k] += 1;
        return lazy[k]%2==0 ? tree[k] : ((actual[k] - tree[k]+1000002022)%1000002022);
      }
      ll mid = (x+y)/2;
      prop(k);
     
      tree[k] = upd(a,b,k*2, x, mid) + upd(a,b,k*2+1, mid+1, y);
      tree[k] %= 1000002022;
      return lazy[k]%2==0 ? tree[k] : ((actual[k] - tree[k]+1000002022)%1000002022);
    }
     
    void init(int N, int M, std::vector<int> P, std::vector<int> A) {
      FOR(i,0,200001) dps[i] = -1;
      FOR(i,0,NN*2) tree[i] = 0, actual[i] = 0, lazy[i] = 0;
      p = P;
      n = N;
      m = M;
      FOR(i,1,N+M){
        edges[P[i]].push_back(i);
      }
      initdfs(0);
     
     
      FOR(i,N,N+M){
        ll temp = possible[i];
        temp *= dp(i);
        contrib[i] = temp%1000002022;
      }
      FOR(i,n,n+m){
        actupd(i-n+1, i-n+1, contrib[i]);
      }
      FOR(i,0,NN*2) tree[i] = actual[i];
      FOR(i,n,n+m){
        if (A[i-n] == 0){
          upd(i-n+1, i-n+1);
        }
      }
     
     
    }
     
     
     
     
     
    int count_ways(int L, int R) {
      upd(L-n+1, R-n+1);
     
     
      return lazy[1]%2==0 ? tree[1] : ((actual[1] - tree[1]+1000002022)%1000002022);
     
    }

Compilation message

circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:105:11: error: no match for 'operator=' (operand types are 'std::__cxx11::basic_string<int>' and 'std::vector<int>')
  105 |       p = P;
      |           ^
In file included from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from circuit.cpp:1:
/usr/include/c++/10/bits/basic_string.h:665:7: note: candidate: 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>& std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::operator=(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&) [with _CharT = int; _Traits = std::char_traits<int>; _Alloc = std::allocator<int>]'
  665 |       operator=(const basic_string& __str)
      |       ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:665:37: note:   no known conversion for argument 1 from 'std::vector<int>' to 'const std::__cxx11::basic_string<int>&'
  665 |       operator=(const basic_string& __str)
      |                 ~~~~~~~~~~~~~~~~~~~~^~~~~
/usr/include/c++/10/bits/basic_string.h:675:7: note: candidate: 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>& std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::operator=(const _CharT*) [with _CharT = int; _Traits = std::char_traits<int>; _Alloc = std::allocator<int>]'
  675 |       operator=(const _CharT* __s)
      |       ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:675:31: note:   no known conversion for argument 1 from 'std::vector<int>' to 'const int*'
  675 |       operator=(const _CharT* __s)
      |                 ~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/basic_string.h:686:7: note: candidate: 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>& std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::operator=(_CharT) [with _CharT = int; _Traits = std::char_traits<int>; _Alloc = std::allocator<int>]'
  686 |       operator=(_CharT __c)
      |       ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:686:24: note:   no known conversion for argument 1 from 'std::vector<int>' to 'int'
  686 |       operator=(_CharT __c)
      |                 ~~~~~~~^~~
/usr/include/c++/10/bits/basic_string.h:703:7: note: candidate: 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>& std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::operator=(std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&&) [with _CharT = int; _Traits = std::char_traits<int>; _Alloc = std::allocator<int>]'
  703 |       operator=(basic_string&& __str)
      |       ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:703:32: note:   no known conversion for argument 1 from 'std::vector<int>' to 'std::__cxx11::basic_string<int>&&'
  703 |       operator=(basic_string&& __str)
      |                 ~~~~~~~~~~~~~~~^~~~~
/usr/include/c++/10/bits/basic_string.h:766:7: note: candidate: 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>& std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::operator=(std::initializer_list<_Tp>) [with _CharT = int; _Traits = std::char_traits<int>; _Alloc = std::allocator<int>]'
  766 |       operator=(initializer_list<_CharT> __l)
      |       ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:766:42: note:   no known conversion for argument 1 from 'std::vector<int>' to 'std::initializer_list<int>'
  766 |       operator=(initializer_list<_CharT> __l)
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/basic_string.h:780:8: note: candidate: 'template<class _Tp> std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::_If_sv<_Tp, std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&> std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::operator=(const _Tp&) [with _Tp = _Tp; _CharT = int; _Traits = std::char_traits<int>; _Alloc = std::allocator<int>]'
  780 |        operator=(const _Tp& __svt)
      |        ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:780:8: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/stl_pair.h:59,
                 from /usr/include/c++/10/bits/stl_algobase.h:64,
                 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 circuit.cpp:1:
/usr/include/c++/10/type_traits: In substitution of 'template<bool _Cond, class _Tp> using enable_if_t = typename std::enable_if::type [with bool _Cond = false; _Tp = std::__cxx11::basic_string<int>&]':
/usr/include/c++/10/bits/basic_string.h:117:8:   required by substitution of 'template<class _CharT, class _Traits, class _Alloc> template<class _Tp, class _Res> using _If_sv = std::enable_if_t<std::__and_<std::is_convertible<const _Tp&, std::basic_string_view<_CharT, _Traits> >, std::__not_<std::is_convertible<const _Tp*, const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>*> >, std::__not_<std::is_convertible<const _Tp&, const _CharT*> > >::value, _Res> [with _Tp = std::vector<int>; _Res = std::__cxx11::basic_string<int>&; _CharT = int; _Traits = std::char_traits<int>; _Alloc = std::allocator<int>]'
/usr/include/c++/10/bits/basic_string.h:780:8:   required by substitution of 'template<class _Tp> std::__cxx11::basic_string<int>::_If_sv<_Tp, std::__cxx11::basic_string<int>&> std::__cxx11::basic_string<int>::operator=<_Tp>(const _Tp&) [with _Tp = std::vector<int>]'
circuit.cpp:105:11:   required from here
/usr/include/c++/10/type_traits:2554:11: error: no type named 'type' in 'struct std::enable_if<false, std::__cxx11::basic_string<int>&>'
 2554 |     using enable_if_t = typename enable_if<_Cond, _Tp>::type;
      |           ^~~~~~~~~~~