Submission #1255853

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255853		biank	Digital Circuit (IOI22_circuit)	C++17	100 / 100	368 ms	35624 KiB

circuit

#include <bits/stdc++.h>

using namespace std;

#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)

#define sz(x) int(x.size())
#define all(x) begin(x), end(x)

using ii = pair<int, int>;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;

#define fst first
#define snd second

#define pb push_back
#define eb emplace_back

const int MAX_N = 2e5 + 9;
const int MOD = 1e9 + 2022;

int mul(int a, int b) {
    return 1LL * a * b % MOD;
}

vi adj[MAX_N];
int val[MAX_N], prod[MAX_N];
int n;

void dfs0(int u) {
    if (u >= n) {
        val[u] = 1;
        return;
    }
    val[u] = sz(adj[u]);
    for (int v : adj[u]) {
        dfs0(v);
        val[u] = mul(val[u], val[v]);
    }
}

void dfs1(int u, int curr) {
    prod[u] = curr;
    const int m = sz(adj[u]);
    vi pref(m + 1), suff(m + 1);
    pref[0] = 1, suff[m] = 1;
    forn(i, m) pref[i + 1] = mul(pref[i], val[adj[u][i]]);
    dforn(i, m) suff[i] = mul(suff[i + 1], val[adj[u][i]]);
    forn(i, m) dfs1(adj[u][i], mul(mul(curr, pref[i]), suff[i + 1]));
}

const int SZ = 1 << 18;

ii st[2 * SZ];
bool lazy[2 * SZ];

void pass(int u) {
    if (u < SZ) {
        lazy[2 * u] ^= lazy[u];
        lazy[2 * u + 1] ^= lazy[u];
    }
    if (lazy[u]) swap(st[u].fst, st[u].snd);
    lazy[u] = false;
}

void calc(int u) {
    st[u].fst = st[2 * u].fst + st[2 * u + 1].fst;
    if (st[u].fst >= MOD) st[u].fst -= MOD;
    st[u].snd = st[2 * u].snd + st[2 * u + 1].snd;
    if (st[u].snd >= MOD) st[u].snd -= MOD;
}

void update(int s, int e, int l = 0, int r = SZ, int u = 1) {
    pass(u);
    if (e <= l || r <= s) return;
    if (s <= l && r <= e) {
        lazy[u] = true;
        return pass(u);
    }
    int m = (l + r) / 2;
    update(s, e, l, m, 2 * u);
    update(s, e, m, r, 2 * u + 1);
    calc(u);
}

void init(int N, int M, vi P, vi A) {
    n = N;
    forsn(i, 1, N + M) adj[P[i]].pb(i);
    dfs0(0);
    dfs1(0, 1);
    forn(i, M) {
        st[i + SZ].fst = prod[i + N];
        st[i + SZ].snd = 0;
        if (!A[i]) swap(st[i + SZ].fst, st[i + SZ].snd);
    }
    dforsn(i, 1, SZ) calc(i);
}

int count_ways(int L, int R) {
    update(L - n, R - n + 1);
    return st[1].fst;
}

• 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