Submission #1222995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222995		cpdreamer	Digital Circuit (IOI22_circuit)	C++20	Compilation error	0 ms	0 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
#define ll long long
#define mod 1000002022
using namespace std;

vector<vector<ll>> adj;
ll n, m;
vector<ll> a;
vector<ll> c;
map<pair<ll, ll>, ll> w;
ll maxn = 3e5;
vector<pair<ll, ll>> tree(4 * maxn + 3);
vector<bool> lazy(4 * maxn + 3);

void push(ll node, ll l, ll r) {
    if (lazy[node]) {
        swap(tree[node].first, tree[node].second);
        if (l != r) {
            lazy[node * 2 + 1] ^= 1;
            lazy[node * 2 + 2] ^= 1;
        }
        lazy[node] = false;
    }
}

void build(ll node, ll l, ll r) {
    if (l == r) {
        if (a[l] == 1) tree[node].first = c[l] % mod;
        else tree[node].second = c[l] % mod;
        return;
    }
    ll mid = (l + r) / 2;
    build(node * 2 + 1, l, mid);
    build(node * 2 + 2, mid + 1, r);
    tree[node].first = (tree[node * 2 + 1].first + tree[node * 2 + 2].first) % mod;
    tree[node].second = (tree[node * 2 + 1].second + tree[node * 2 + 2].second) % mod;
}

void update(ll node, ll l, ll r, ll x, ll y) {
    push(node, l, r);
    if (r < x || l > y) return;
    if (x <= l && r <= y) {
        lazy[node] ^= 1;
        push(node, l, r);
        return;
    }
    ll mid = (l + r) / 2;
    update(node * 2 + 1, l, mid, x, y);
    update(node * 2 + 2, mid + 1, r, x, y);
    tree[node].first = (tree[node * 2 + 1].first + tree[node * 2 + 2].first) % mod;
    tree[node].second = (tree[node * 2 + 1].second + tree[node * 2 + 2].second) % mod;
}

ll dfs(ll node, ll par) {
    if (adj[node].size() == 1 && node != par) return 1;
    vector<ll> children;
    for (ll u : adj[node]) if (u != par) children.push_back(u);

    int k = children.size();
    vector<ll> v(k), pre(k), suf(k);

    for (int i = 0; i < k; i++) {
        v[i] = dfs(children[i], node);
    }

    pre[0] = v[0];
    for (int i = 1; i < k; i++) {
        pre[i] = (pre[i - 1] * v[i]) % mod;
    }

    suf[k - 1] = v[k - 1];
    for (int i = k - 2; i >= 0; i--) {
        suf[i] = (suf[i + 1] * v[i]) % mod;
    }

    for (int i = 0; i < k; i++) {
        ll val = 1;
        if (i > 0) val = (val * pre[i - 1]) % mod;
        if (i + 1 < k) val = (val * suf[i + 1]) % mod;
        w[{node, children[i]}] = val;
        w[{children[i], node}] = val;
    }

    ll total = 1;
    for (int i = 0; i < k; i++) {
        total = (total * v[i]) % mod;
    }
    return (total * adj[node].size()) % mod;
}

void calculate(ll node, ll par, ll pr) {
    if (adj[node].size() == 1 && node != par) {
        c[node - n] = pr;
        return;
    }
    for (ll u : adj[node]) {
        if (u == par) continue;
        calculate(u, node, (pr * w[{node, u}]) % mod);
    }
}

void init(int N, int M, vector<int> P, vector<int> A) {
    n = N;
    m = M;
    a = vector<ll>(A.begin(), A.end());
    c.assign(m, 1);
    adj.assign(n + m, {});

    for (int i = 1; i < n + m; i++) {
        adj[i].push_back(P[i]);
        adj[P[i]].push_back(i);
    }

    dfs(0, 0);
    calculate(0, 0, 1);
    build(0, 0, m - 1);
}

int count_ways(int L, int R) {
    update(0, 0, m - 1, L - n, R - n);
    push(0, 0, m - 1);
    return tree[0].first;
}

Compilation message (stderr)

circuit.cpp: In function 'void push(long long int, long long int, long long int)':
circuit.cpp:20:32: error: no match for 'operator^=' (operand types are 'std::vector<bool>::reference' and 'int')
   20 |             lazy[node * 2 + 1] ^= 1;
      |             ~~~~~~~~~~~~~~~~~~~^~~~
In file included from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:45,
                 from circuit.cpp:2:
/usr/include/c++/11/cstddef:179:3: note: candidate: 'constexpr std::byte& std::operator^=(std::byte&, std::byte)'
  179 |   operator^=(byte& __l, byte __r) noexcept
      |   ^~~~~~~~
/usr/include/c++/11/cstddef:179:20: note:   no known conversion for argument 1 from 'std::vector<bool>::reference' to 'std::byte&'
  179 |   operator^=(byte& __l, byte __r) noexcept
      |              ~~~~~~^~~
In file included from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from circuit.cpp:2:
/usr/include/c++/11/bits/ios_base.h:107:3: note: candidate: 'const std::_Ios_Fmtflags& std::operator^=(std::_Ios_Fmtflags&, std::_Ios_Fmtflags)'
  107 |   operator^=(_Ios_Fmtflags& __a, _Ios_Fmtflags __b)
      |   ^~~~~~~~
/usr/include/c++/11/bits/ios_base.h:107:29: note:   no known conversion for argument 1 from 'std::vector<bool>::reference' to 'std::_Ios_Fmtflags&'
  107 |   operator^=(_Ios_Fmtflags& __a, _Ios_Fmtflags __b)
      |              ~~~~~~~~~~~~~~~^~~
/usr/include/c++/11/bits/ios_base.h:149:3: note: candidate: 'const std::_Ios_Openmode& std::operator^=(std::_Ios_Openmode&, std::_Ios_Openmode)'
  149 |   operator^=(_Ios_Openmode& __a, _Ios_Openmode __b)
      |   ^~~~~~~~
/usr/include/c++/11/bits/ios_base.h:149:29: note:   no known conversion for argument 1 from 'std::vector<bool>::reference' to 'std::_Ios_Openmode&'
  149 |   operator^=(_Ios_Openmode& __a, _Ios_Openmode __b)
      |              ~~~~~~~~~~~~~~~^~~
/usr/include/c++/11/bits/ios_base.h:189:3: note: candidate: 'const std::_Ios_Iostate& std::operator^=(std::_Ios_Iostate&, std::_Ios_Iostate)'
  189 |   operator^=(_Ios_Iostate& __a, _Ios_Iostate __b)
      |   ^~~~~~~~
/usr/include/c++/11/bits/ios_base.h:189:28: note:   no known conversion for argument 1 from 'std::vector<bool>::reference' to 'std::_Ios_Iostate&'
  189 |   operator^=(_Ios_Iostate& __a, _Ios_Iostate __b)
      |              ~~~~~~~~~~~~~~^~~
In file included from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:105,
                 from circuit.cpp:2:
/usr/include/c++/11/future:169:18: note: candidate: 'std::launch& std::operator^=(std::launch&, std::launch)'
  169 |   inline launch& operator^=(launch& __x, launch __y) noexcept
      |                  ^~~~~~~~
/usr/include/c++/11/future:169:37: note:   no known conversion for argument 1 from 'std::vector<bool>::reference' to 'std::launch&'
  169 |   inline launch& operator^=(launch& __x, launch __y) noexcept
      |                             ~~~~~~~~^~~
In file included from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:127,
                 from circuit.cpp:2:
/usr/include/c++/11/charconv:686:3: note: candidate: 'constexpr std::chars_format& std::operator^=(std::chars_format&, std::chars_format)'
  686 |   operator^=(chars_format& __lhs, chars_format __rhs) noexcept
      |   ^~~~~~~~
/usr/include/c++/11/charconv:686:28: note:   no known conversion for argument 1 from 'std::vector<bool>::reference' to 'std::chars_format&'
  686 |   operator^=(chars_format& __lhs, chars_format __rhs) noexcept
      |              ~~~~~~~~~~~~~~^~~~~
circuit.cpp:21:32: error: no match for 'operator^=' (operand types are 'std::vector<bool>::reference' and 'int')
   21 |             lazy[node * 2 + 2] ^= 1;
      |             ~~~~~~~~~~~~~~~~~~~^~~~
In file included from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:45,
                 from circuit.cpp:2:
/usr/include/c++/11/cstddef:179:3: note: candidate: 'constexpr std::byte& std::operator^=(std::byte&, std::byte)'
  179 |   operator^=(byte& __l, byte __r) noexcept
      |   ^~~~~~~~
/usr/include/c++/11/cstddef:179:20: note:   no known conversion for argument 1 from 'std::vector<bool>::reference' to 'std::byte&'
  179 |   operator^=(byte& __l, byte __r) noexcept
      |              ~~~~~~^~~
In file included from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from circuit.cpp:2:
/usr/include/c++/11/bits/ios_base.h:107:3: note: candidate: 'const std::_Ios_Fmtflags& std::operator^=(std::_Ios_Fmtflags&, std::_Ios_Fmtflags)'
  107 |   operator^=(_Ios_Fmtflags& __a, _Ios_Fmtflags __b)
      |   ^~~~~~~~
/usr/include/c++/11/bits/ios_base.h:107:29: note:   no known conversion for argument 1 from 'std::vector<bool>::reference' to 'std::_Ios_Fmtflags&'
  107 |   operator^=(_Ios_Fmtflags& __a, _Ios_Fmtflags __b)
      |              ~~~~~~~~~~~~~~~^~~
/usr/include/c++/11/bits/ios_base.h:149:3: note: candidate: 'const std::_Ios_Openmode& std::operator^=(std::_Ios_Openmode&, std::_Ios_Openmode)'
  149 |   operator^=(_Ios_Openmode& __a, _Ios_Openmode __b)
      |   ^~~~~~~~
/usr/include/c++/11/bits/ios_base.h:149:29: note:   no known conversion for argument 1 from 'std::vector<bool>::reference' to 'std::_Ios_Openmode&'
  149 |   operator^=(_Ios_Openmode& __a, _Ios_Openmode __b)
      |              ~~~~~~~~~~~~~~~^~~
/usr/include/c++/11/bits/ios_base.h:189:3: note: candidate: 'const std::_Ios_Iostate& std::operator^=(std::_Ios_Iostate&, std::_Ios_Iostate)'
  189 |   operator^=(_Ios_Iostate& __a, _Ios_Iostate __b)
      |   ^~~~~~~~
/usr/include/c++/11/bits/ios_base.h:189:28: note:   no known conversion for argument 1 from 'std::vector<bool>::reference' to 'std::_Ios_Iostate&'
  189 |   operator^=(_Ios_Iostate& __a, _Ios_Iostate __b)
      |              ~~~~~~~~~~~~~~^~~
In file included from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:105,
                 from circuit.cpp:2:
/usr/include/c++/11/future:169:18: note: candidate: 'std::launch& std::operator^=(std::launch&, std::launch)'
  169 |   inline launch& operator^=(launch& __x, launch __y) noexcept
      |                  ^~~~~~~~
/usr/include/c++/11/future:169:37: note:   no known conversion for argument 1 from 'std::vector<bool>::reference' to 'std::launch&'
  169 |   inline launch& operator^=(launch& __x, launch __y) noexcept
      |                             ~~~~~~~~^~~
In file included from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:127,
                 from circuit.cpp:2:
/usr/include/c++/11/charconv:686:3: note: candidate: 'constexpr std::chars_format& std::operator^=(std::chars_format&, std::chars_format)'
  686 |   operator^=(chars_format& __lhs, chars_format __rhs) noexcept
      |   ^~~~~~~~
/usr/include/c++/11/charconv:686:28: note:   no known conversion for argument 1 from 'std::vector<bool>::reference' to 'std::chars_format&'
  686 |   operator^=(chars_format& __lhs, chars_format __rhs) noexcept
      |              ~~~~~~~~~~~~~~^~~~~
circuit.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int)':
circuit.cpp:44:20: error: no match for 'operator^=' (operand types are 'std::vector<bool>::reference' and 'int')
   44 |         lazy[node] ^= 1;
      |         ~~~~~~~~~~~^~~~
In file included from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:45,
                 from circuit.cpp:2:
/usr/include/c++/11/cstddef:179:3: note: candidate: 'constexpr std::byte& std::operator^=(std::byte&, std::byte)'
  179 |   operator^=(byte& __l, byte __r) noexcept
      |   ^~~~~~~~
/usr/include/c++/11/cstddef:179:20: note:   no known conversion for argument 1 from 'std::vector<bool>::reference' to 'std::byte&'
  179 |   operator^=(byte& __l, byte __r) noexcept
      |              ~~~~~~^~~
In file included from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from circuit.cpp:2:
/usr/include/c++/11/bits/ios_base.h:107:3: note: candidate: 'const std::_Ios_Fmtflags& std::operator^=(std::_Ios_Fmtflags&, std::_Ios_Fmtflags)'
  107 |   operator^=(_Ios_Fmtflags& __a, _Ios_Fmtflags __b)
      |   ^~~~~~~~
/usr/include/c++/11/bits/ios_base.h:107:29: note:   no known conversion for argument 1 from 'std::vector<bool>::reference' to 'std::_Ios_Fmtflags&'
  107 |   operator^=(_Ios_Fmtflags& __a, _Ios_Fmtflags __b)
      |              ~~~~~~~~~~~~~~~^~~
/usr/include/c++/11/bits/ios_base.h:149:3: note: candidate: 'const std::_Ios_Openmode& std::operator^=(std::_Ios_Openmode&, std::_Ios_Openmode)'
  149 |   operator^=(_Ios_Openmode& __a, _Ios_Openmode __b)
      |   ^~~~~~~~
/usr/include/c++/11/bits/ios_base.h:149:29: note:   no known conversion for argument 1 from 'std::vector<bool>::reference' to 'std::_Ios_Openmode&'
  149 |   operator^=(_Ios_Openmode& __a, _Ios_Openmode __b)
      |              ~~~~~~~~~~~~~~~^~~
/usr/include/c++/11/bits/ios_base.h:189:3: note: candidate: 'const std::_Ios_Iostate& std::operator^=(std::_Ios_Iostate&, std::_Ios_Iostate)'
  189 |   operator^=(_Ios_Iostate& __a, _Ios_Iostate __b)
      |   ^~~~~~~~
/usr/include/c++/11/bits/ios_base.h:189:28: note:   no known conversion for argument 1 from 'std::vector<bool>::reference' to 'std::_Ios_Iostate&'
  189 |   operator^=(_Ios_Iostate& __a, _Ios_Iostate __b)
      |              ~~~~~~~~~~~~~~^~~
In file included from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:105,
                 from circuit.cpp:2:
/usr/include/c++/11/future:169:18: note: candidate: 'std::launch& std::operator^=(std::launch&, std::launch)'
  169 |   inline launch& operator^=(launch& __x, launch __y) noexcept
      |                  ^~~~~~~~
/usr/include/c++/11/future:169:37: note:   no known conversion for argument 1 from 'std::vector<bool>::reference' to 'std::launch&'
  169 |   inline launch& operator^=(launch& __x, launch __y) noexcept
      |                             ~~~~~~~~^~~
In file included from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:127,
                 from circuit.cpp:2:
/usr/include/c++/11/charconv:686:3: note: candidate: 'constexpr std::chars_format& std::operator^=(std::chars_format&, std::chars_format)'
  686 |   operator^=(chars_format& __lhs, chars_format __rhs) noexcept
      |   ^~~~~~~~
/usr/include/c++/11/charconv:686:28: note:   no known conversion for argument 1 from 'std::vector<bool>::reference' to 'std::chars_format&'
  686 |   operator^=(chars_format& __lhs, chars_format __rhs) noexcept
      |              ~~~~~~~~~~~~~~^~~~~