Submission #1224165

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224165		Sharky	Digital Circuit (IOI22_circuit)	C++20	100 / 100	365 ms	37104 KiB

circuit

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

using i32 = int32_t;
#define int long long

const int MAXN = 2e5 + 5;
const int mod = 1000002022;

int n, m, dp[MAXN], a[MAXN], all[MAXN], mul[MAXN];
vector<int> adj[MAXN];

void Dfs(int u) {
    if (u >= n) all[u] = 1;
    else all[u] = adj[u].size();
    for (auto& v : adj[u]) {
        Dfs(v);
        (all[u] *= all[v]) %= mod;
    }
}

inline int add(int x, int y) {
    x += y;
    if (x >= mod) x -= mod;
    return x;
}

struct SegTree {
    int size = 1;
    vector<int> seg, off, lazy;
    void init(int sz) {
        while (size < sz) size *= 2;
        seg.assign(2 * size + 10, 0);
        off.assign(2 * size + 10, 0);
        lazy.assign(2 * size + 10, 0);
    }
    void push(int id) {
        if (lazy[id]) {
            swap(seg[id], off[id]);
            if (id < size) {
                for (int i = 0; i < 2; i++) {
                    lazy[id * 2 + i] ^= 1;
                }
            }
        }
        lazy[id] = 0;
    }
    void pull(int id) {
        seg[id] = add(seg[id * 2], seg[id * 2 + 1]);
        off[id] = add(off[id * 2], off[id * 2 + 1]);
    }
    void build(int l, int r, int id) {
        if (l == r) {
            if (a[l + n]) {
                seg[id] = mul[l + n];
                off[id] = 0;
            } else {
                seg[id] = 0;
                off[id] = mul[l + n];
            }
            return;
        }
        int mid = (l + r) / 2;
        build(l, mid, id * 2);
        build(mid + 1, r, id * 2 + 1);
        pull(id);
    }
    void update(int ql, int qr, int l, int r, int id) {
        push(id);
        if (ql <= l && r <= qr) {
            lazy[id] = 1;
            push(id);
            return;
        }
        if (qr < l || r < ql) return;
        int mid = (l + r) / 2;
        update(ql, qr, l, mid, id * 2);
        update(ql, qr, mid + 1, r, id * 2 + 1);
        pull(id);
    }
    int query() {
        push(1);
        return seg[1];
    }
} sgt;

void dfs(int u) {
    if (u >= n) return;
    int sz = adj[u].size();
    vector<int> pref(sz, 0), suff(sz, 0);
    for (int i = 0; i < sz; i++) {
        pref[i] = all[adj[u][i]];
        if (i) (pref[i] *= pref[i - 1]) %= mod;
    }
    for (int i = sz - 1; i >= 0; i--) {
        suff[i] = all[adj[u][i]];
        if (i + 1 < sz) (suff[i] *= suff[i + 1]) %= mod;
    }
    for (int i = 0; i < sz; i++) {
        int res = 1;
        if (i) res = pref[i - 1];
        if (i + 1 < sz) (res *= suff[i + 1]) %= mod;
        (res *= mul[u]) %= mod;
        mul[adj[u][i]] = res;
        dfs(adj[u][i]);
    }
}

void init(i32 N, i32 M, std::vector<i32> P, std::vector<i32> A) {
    n = N;
    m = M;
    for (int i = 0; i < m; i++) a[i + n] = A[i];
    for (int i = 1; i < n + m; i++) adj[P[i]].push_back(i);
    Dfs(0);
    mul[0] = 1;
    dfs(0);
    sgt.init(m + 1);
    sgt.build(0, m - 1, 1);
}

i32 count_ways(i32 L, i32 R) {
    sgt.update(L - n, R - n, 0, m - 1, 1);
    return sgt.query();
}

• 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