Submission #820089

#	Time	Username	Problem	Language	Result	Execution time	Memory
820089		finn__	Digital Circuit (IOI22_circuit)	C++17	100 / 100	941 ms	39276 KiB

circuit

#include <bits/stdc++.h>

#include "circuit.h"

using namespace std;

constexpr int64_t MOD = 1'000'002'022;

template <size_t L>
struct segment_tree
{
    int64_t t[L << 1], sum[L << 1];
    bitset<L << 1> lazy;

    void propagate(size_t k)
    {
        if (lazy[k])
        {
            t[k << 1] = (sum[k << 1] - t[k << 1] + MOD) % MOD;
            t[k << 1 | 1] = (sum[k << 1 | 1] - t[k << 1 | 1] + MOD) % MOD;
            lazy[k << 1] = !lazy[k << 1];
            lazy[k << 1 | 1] = !lazy[k << 1 | 1];
            lazy[k] = 0;
        }
    }

    void flip(size_t i, size_t j, size_t k = 1, size_t a = 0, size_t b = L - 1)
    {
        if (b < i || a > j)
            return;
        if (i <= a && b <= j)
        {
            lazy[k] = !lazy[k];
            t[k] = (sum[k] - t[k] + MOD) % MOD;
        }
        else
        {
            propagate(k);
            flip(i, j, k << 1, a, (a + b) >> 1);
            flip(i, j, k << 1 | 1, ((a + b) >> 1) + 1, b);
            t[k] = (t[k << 1] + t[k << 1 | 1]) % MOD;
        }
    }

    void build_sum()
    {
        for (size_t i = L - 1; i; --i)
            sum[i] = (sum[i << 1] + sum[i << 1 | 1]) % MOD;
    }
};

constexpr size_t N = 200000, L = 1 << 18;

size_t n, m;
segment_tree<L> tree;
bitset<N> state;
vector<size_t> g[N];
int64_t num_children_prod[N];

void find_num_children_prod(size_t u)
{
    if (g[u].empty())
    {
        num_children_prod[u] = 1;
        return;
    }

    num_children_prod[u] = g[u].size();
    for (auto const &v : g[u])
    {
        find_num_children_prod(v);
        num_children_prod[u] = (num_children_prod[u] * num_children_prod[v]) % MOD;
    }
}

void dfs(size_t u, int64_t prod = 1)
{
    if (g[u].empty())
    {
        tree.sum[L + u] = prod;
        return;
    }

    vector<int64_t> pre(g[u].size()), suf(g[u].size());

    pre[0] = 1;
    for (size_t i = 1; i < pre.size(); ++i)
        pre[i] = (pre[i - 1] * num_children_prod[g[u][i - 1]]) % MOD;

    suf[suf.size() - 1] = 1;
    for (size_t i = suf.size() - 2; i < suf.size(); --i)
        suf[i] = (suf[i + 1] * num_children_prod[g[u][i + 1]]) % MOD;

    for (size_t i = 0; i < g[u].size(); ++i)
    {
        auto const &v = g[u][i];
        dfs(v, (((prod * pre[i]) % MOD) * suf[i]) % MOD);
    }
}

void init(int n_, int m_, vector<int> p, vector<int> a)
{
    n = n_, m = m_;
    for (size_t i = 0; i < p.size(); ++i)
        if (p[i] != -1)
            g[p[i]].push_back(i);

    find_num_children_prod(0);
    dfs(0);
    tree.build_sum();
    for (size_t i = 0; i < a.size(); ++i)
        if (state[n + i] = a[i])
            tree.flip(n + i, n + i);
}

int count_ways(int l, int r)
{
    tree.flip(l, r);
    return tree.t[1];
}

• 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