Submission #627401

#	Time	Username	Problem	Language	Result	Execution time	Memory
627401		phathnv	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1771 ms	34192 KiB

circuit

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

const int N = 2e5 + 10;
const int MOD = 1e9 + 2022;

struct Segtree {
    int n;
    vector<array<int, 2>> a;
    vector<int> lazy;
    void init(int _n, const vector<array<int, 2>> &val) {
        n = _n;
        a.assign(4 * n + 1, {0, 0});
        lazy.assign(4 * n + 1, 0);
        build(1, 0, n - 1, val);
    }
    void build(int id, int l, int r, const vector<array<int, 2>> &val) {
        if (l == r) {
            a[id] = val[l];
            cerr << "build " << a[id][0] << ' ' << a[id][1] << endl;
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid, val);
        build(id << 1 | 1, mid + 1, r, val);
        a[id][0] = (a[id << 1][0] + a[id << 1 | 1][0]) % MOD;
        a[id][1] = (a[id << 1][1] + a[id << 1 | 1][1]) % MOD;
    }
    void doLazy(int id, int l, int r) {
        if (lazy[id]) {
            swap(a[id][0], a[id][1]);
            if (l < r) {
                lazy[id << 1] ^= lazy[id];
                lazy[id << 1 | 1] ^= lazy[id];
            }
            lazy[id] = 0;
        }
    }
    void update(int id, int l, int r, int u, int v) {
        doLazy(id, l, r);
        if (v < l || r < u) {
            return;
        }
        if (u <= l && r <= v) {
            lazy[id] ^= 1;
            doLazy(id, l, r);
            return;
        }
        int mid = (l + r) >> 1;
        update(id << 1, l, mid, u, v);
        update(id << 1 | 1, mid + 1, r, u, v);
        a[id][0] = (a[id << 1][0] + a[id << 1 | 1][0]) % MOD;
        a[id][1] = (a[id << 1][1] + a[id << 1 | 1][1]) % MOD;
    }
    void update(int l, int r) {
        update(1, 0, n - 1, l, r);
    }
    void debug(int id, int l, int r) {
        doLazy(id, l, r);
        if (l == r) {
            return;
        }
        int mid = (l + r) >> 1;
        debug(id << 1, l, mid);
        debug(id << 1 | 1, mid + 1, r);
    }
    int get() {
        doLazy(1, 0, n - 1);
        return a[1][0];
    }
} ST;

int n, m, c[N], f[N];
vector<int> childs[N];

void dfs1(int u) {
    if (childs[u].empty()) {
        c[u] = 1;
        return;
    }
    c[u] = childs[u].size();
    for (int v : childs[u]) {
        dfs1(v);
        c[u] = 1ll * c[u] * c[v] % MOD;
    }
}

void dfs2(int u) {
    if (childs[u].empty()) {
        return;
    }
    int n = childs[u].size();
    vector<int> l(n), r(n);
    l[0] = 1;
    for (int i = 1; i < n; ++i) {
        l[i] = 1ll * l[i - 1] * c[childs[u][i - 1]] % MOD;
    }
    r[n - 1] = 1;
    for (int i = n - 2; i >= 0; --i) {
        r[i] = 1ll * r[i + 1] * c[childs[u][i + 1]] % MOD;
    }
    for (int i = 0; i < n; ++i) {
        int v = childs[u][i];
        f[v] = 1ll * l[i] * r[i] % MOD;
        dfs2(v);
    }
}

void dfs3(int u) {
    for (int v : childs[u]) {
        f[v] = 1ll * f[v] * f[u] % MOD;
        dfs3(v);
    }
}

void init(int _n, int _m, vector<int> p, vector<int> a) {
    n = _n;
    m = _m;
    for (int i = 1; i < m + n; ++i) {
        childs[p[i]].push_back(i);
    }

    dfs1(0);
    fill(f, f + N, 1);
    dfs2(0);
    dfs3(0);

    vector<array<int, 2>> val;
    for (int i = n; i < m + n; ++i) {
        if (a[i - n] == 1) {
            val.push_back({f[i], 0});
        } else {
            val.push_back({0, f[i]});
        }
    }

    ST.init(m, val);
}

int count_ways(int l, int r) {
    ST.update(l - n, r - n);
    return ST.get();
}

• 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