Submission #798061

#	Time	Username	Problem	Language	Result	Execution time	Memory
798061		jakobrs	Digital Circuit (IOI22_circuit)	C++17	100 / 100	940 ms	37144 KiB

circuit

#include <iostream>
#include <vector>

using i64 = int64_t;

const i64 MOD = 1'000'002'022;

struct Node {
    i64 a1, a0;

    Node() : a1(0), a0(0) {}
    Node(i64 a1, i64 a0) : a1(a1), a0(a0) {}

    void toggle() { std::swap(a1, a0); }

    Node operator*(const Node &rhs) const {
        return {(a1 + rhs.a1) % MOD, (a0 + rhs.a0) % MOD};
    }

    // Node operator*(const Node &rhs) const {
    //     return {(a1 * rhs.ax + ax * rhs.a1) % MOD,
    //             (a0 * rhs.ax + ax * rhs.a0) % MOD, ax * rhs.ax * 2 % MOD};
    // }
};

struct SegmentTree {
    std::vector<Node> values;
    std::vector<bool> toggled;
    i64 offset;

    SegmentTree() : values{}, toggled{}, offset{0} {}
    explicit SegmentTree(size_t sz, const std::vector<i64> contribution)
        : values(2 * sz), toggled(2 * sz, false), offset(sz) {
        for (i64 i = 0; i < sz; i++) {
            i64 c = i < contribution.size() ? contribution[i] : 0;
            values[sz + i] = Node(0, c);
        }

        for (i64 i = sz - 1; i > 0; i--) pull(i);
    }

    void toggle(i64 idx) {
        idx += offset;

        values[idx].toggle();

        while (idx /= 2) pull(idx);
    }

    void toggle_range(i64 l, i64 r) { toggle_range(l, r, 1, 0, offset); }
    void toggle_range(i64 l, i64 r, i64 v, i64 s, i64 e) {
        if (e <= l || r <= s) {
            return;
        } else if (l <= s && e <= r) {
            values[v].toggle();
            toggled[v] = !toggled[v];
        } else {
            i64 m = (s + e) / 2;

            push(v);
            toggle_range(l, r, 2 * v, s, m);
            toggle_range(l, r, 2 * v + 1, m, e);
            pull(v);
        }
    }

    void push(i64 v) {
        if (toggled[v]) {
            toggled[v] = false;

            toggled[2 * v] = !toggled[2 * v];
            toggled[2 * v + 1] = !toggled[2 * v + 1];

            values[2 * v].toggle();
            values[2 * v + 1].toggle();
        }
    }

    void pull(i64 v) { values[v] = values[2 * v] * values[2 * v + 1]; }

    const Node &root() const { return values[1]; }
};

int n, m;
std::vector<int> p, a;

std::vector<std::vector<int>> children;
std::vector<i64> possible;
std::vector<i64> contribution;
SegmentTree st;

i64 &dfs(int node) {
    if (node >= n) return possible[node] = 1;

    i64 total = children[node].size();

    for (i64 c : children[node]) {
        total *= dfs(c);
        total %= MOD;
    }

    return possible[node] = total;
}
void dfs1(int node, int contrib) {
    if (node >= n) {
        contribution[node - n] = contrib;
        return;
    }

    // std::cerr << node << ' ' << children.size() << ' ' << n << '\n';
    i64 cs = children[node].size();
    std::vector<i64> xs_left{1}, xs_right{1};
    xs_left.reserve(1 + cs);
    xs_right.reserve(1 + cs);

    for (i64 i = 0; i < cs; i++) {
        xs_left.push_back(xs_left.back() * possible[children[node][i]] % MOD);
        xs_right.push_back(xs_right.back() *
                           possible[children[node][cs - i - 1]] % MOD);
    }

    for (i64 i = 0; i < cs; i++) {
        dfs1(children[node][i],
             contrib * xs_left[i] % MOD * xs_right[cs - i - 1] % MOD);
    }
}

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    n = N;
    m = M;
    p = P;
    a = A;

    children.resize(N);
    for (i64 i = 1; i < N + M; i++) {
        children[P[i]].push_back(i);
    }

    possible.resize(N + M);
    dfs(0);
    contribution.resize(M);
    dfs1(0, 1);

    i64 o = 1;
    while (o < M) o *= 2;
    st = SegmentTree(o, contribution);

    for (i64 i = 0; i < M; i++) {
        if (A[i]) st.toggle(i);
    }
}

int count_ways(int l, int r) {
    r += 1;

    l -= n;
    r -= n;

    st.toggle_range(l, r);

    return st.root().a1;
}

Compilation message (stderr)

circuit.cpp: In constructor 'SegmentTree::SegmentTree(size_t, std::vector<long int>)':
circuit.cpp:34:27: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long int'} and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for (i64 i = 0; i < sz; i++) {
      |                         ~~^~~~
circuit.cpp:35:23: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |             i64 c = i < contribution.size() ? contribution[i] : 0;
      |                     ~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 4 / 4
• Subtask 5: 12 / 12
• Subtask 6: 27 / 27
• Subtask 7: 28 / 28
• Subtask 8: 11 / 11