Submission #1212269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212269		mmario99	Digital Circuit (IOI22_circuit)	C++20	100 / 100	343 ms	27784 KiB

circuit

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

static const ll MOD = 1000002022;

static int gN, gM;
static vector<int> parentArr;
static vector<vector<int>> children;
static vector<ll> Sval;
static vector<ll> Wval;
static vector<ll> upVal;
static vector<ll> coef;
static vector<int> leafState;
struct SegTree
{
    int n;
    struct Node
    {
        ll sum;
        ll totCoef;
        bool flip;
    };
    vector<Node> st;

    SegTree(int _n = 0) : n(_n)
    {
        if (n > 0)
            st.resize(4 * n);
    }

    void build(int p, int l, int r)
    {
        if (l == r)
        {
            st[p].totCoef = coef[l] % MOD;
            st[p].sum     = (coef[l] * leafState[l]) % MOD;
            st[p].flip    = false;
            return;
        }
        int m = (l + r) >> 1;
        build(p << 1,   l,   m);
        build(p << 1 | 1, m + 1, r);
        st[p].totCoef = (st[p << 1].totCoef + st[p << 1 | 1].totCoef) % MOD;
        st[p].sum     = (st[p << 1].sum     + st[p << 1 | 1].sum)     % MOD;
        st[p].flip    = false;
    }

    inline void applyFlip(int p)
    {
        st[p].sum = (st[p].totCoef - st[p].sum) % MOD;
        if (st[p].sum < 0) st[p].sum += MOD;
        st[p].flip = !st[p].flip;
    }

    inline void push(int p)
    {
        if (!st[p].flip) return;
        applyFlip(p << 1);
        applyFlip(p << 1 | 1);
        st[p].flip = false;
    }

    void updateRange(int p, int l, int r, int i, int j)
    {
        if (j < l || i > r) return;
        if (l >= i && r <= j)
        {
            applyFlip(p);
            return;
        }
        push(p);
        int m = (l + r) >> 1;
        updateRange(p << 1,   l,   m, i, j);
        updateRange(p << 1 | 1, m + 1, r, i, j);
        st[p].sum = (st[p << 1].sum + st[p << 1 | 1].sum) % MOD;
    }

    void init_build(int _n)
    {
        n = _n;
        st.resize(4 * n);
        build(1, 0, n - 1);
    }

    void invertInterval(int L, int R)
    {
        updateRange(1, 0, n - 1, L, R);
    }

    ll queryAll() const
    {
        return st[1].sum;
    }
};

static SegTree seg;

void init(int N, int M, std::vector <int> P, std::vector <int> A)
{
    gN = N;
    gM = M;

    parentArr.resize(N + M);
    for (int i = 0; i < N + M; i++)
    {
        parentArr[i] = P[i];
    }
    children.assign(N + M, {});
    for (int i = 1; i < N + M; i++)
    {
        int p = parentArr[i];
        children[p].push_back(i);
    }
    leafState.resize(M);
    for (int i = 0; i < M; i++)
    {
        leafState[i] = A[i];
    }
    Sval.assign(N + M, 0LL);
    for (int v = N + M - 1; v >= 0; v--)
    {
        if (v >= N)
        {
            // Leaf
            Sval[v] = 1;
        }
        else
        {
            ll prod = 1;
            int d = (int)children[v].size();
            for (int c : children[v])
            {
                prod = (prod * Sval[c]) % MOD;
            }
            prod = (prod * d) % MOD;
            Sval[v] = prod;
        }
    }
    Wval.assign(N + M, 1LL);
    for (int v = 0; v < N; v++)
    {
        int d = (int)children[v].size();
        if (d == 0) continue;
        vector<ll> pref(d), suf(d);
        for (int i = 0; i < d; i++)
        {
            pref[i] = Sval[children[v][i]];
            suf[i] = pref[i];
        }
        for (int i = 1; i < d; i++)
        {
            pref[i] = (pref[i] * pref[i - 1]) % MOD;
        }
        for (int i = d - 2; i >= 0; i--)
        {
            suf[i] = (suf[i] * suf[i + 1]) % MOD;
        }
        for (int i = 0; i < d; i++)
        {
            ll left = (i > 0    ? pref[i - 1] : 1LL);
            ll right = (i + 1 < d ? suf[i + 1] : 1LL);
            ll w = (left * right) % MOD;
            int c = children[v][i];
            Wval[c] = w;
        }
    }
    Wval[0] = 1;
    upVal.assign(N + M, 1LL);
    vector<int> bfs;
    bfs.reserve(N + M);
    bfs.push_back(0);
    for (int idx = 0; idx < (int)bfs.size(); idx++)
    {
        int v = bfs[idx];
        for (int c : children[v])
        {
            upVal[c] = (upVal[v] * Wval[c]) % MOD;
            bfs.push_back(c);
        }
    }

    coef.assign(M, 0LL);
    for (int i = 0; i < M; i++)
    {
        coef[i] = upVal[N + i];
    }
    seg = SegTree(M);
    seg.init_build(M);
}
int count_ways(int L, int R)
{
    int l = L - gN;
    int r = R - gN;
    seg.invertInterval(l, r);
    ll ans = seg.queryAll() % MOD;
    return int(ans);
}

• 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