Submission #1236882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236882		countless	Digital Circuit (IOI22_circuit)	C++20	0 / 100	210 ms	7208 KiB

circuit

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

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"

const ll MOD = 1000002022;
const int MAXN = 2e5+5;

int n, m;
vector<vector<int>> down;
vector<int> up;
vector<int> a;
vector<bool> lazy;
ll dp[MAXN][2];

void update(int node, int l, int r, int ql, int qr) {
    if (ql > r or qr < l) return;
    if (ql <= l and r <= qr) {
        lazy[node] = !lazy[node];
        swap(dp[node][0], dp[node][1]);
        return;
    }

    int m = (l+r) / 2;
    int left = down[node].front(), right = down[node].back();
    if (lazy[node]) {
        lazy[node] = false;
        lazy[left] = !lazy[left];
        swap(dp[left][0], dp[left][1]);
        lazy[right] = !lazy[right];
        swap(dp[right][0], dp[right][1]);
    }

    update(left, l, m, ql, qr);
    update(right, m+1, r, ql, qr);

    auto [l0, l1] = dp[left];
    auto [r0, r1] = dp[right];

    dp[node][0] = ((l0*r1) % MOD + (l1*r0) % MOD + (2LL*l0*r0) % MOD) % MOD;
    dp[node][1] = ((l0*r1) % MOD + (l1*r0) % MOD + (2LL*l1*r1) % MOD) % MOD;
}

void init(int N, int M, vector<int> P, vector<int> A) {
    memset(&dp[0][0], 0, sizeof(dp));
    down.assign(N+M, {});
    lazy.assign(N+M, false);
    n = N, m = M, up = P, a = A;

    for (int i = 1; i < N + M; i++) {
        down[P[i]].push_back(i);
    }

    auto dfs = [&](auto &&dfs, int u) -> void {
        if (down[u].empty()) {
            dp[u][0] = a[u-n] == 0;
            dp[u][1] = a[u-n] == 1;
            return;
        }

        // two children
        assert(down[u].size() == 2);
        int l = down[u].front(), r = down[u].back();
        dfs(dfs, l); dfs(dfs, r);
        auto [l0, l1] = dp[l];
        auto [r0, r1] = dp[r];

        dp[u][0] = ((l0*r1) % MOD + (l1*r0) % MOD + (2LL*l0*r0) % MOD) % MOD;
        dp[u][1] = ((l0*r1) % MOD + (l1*r0) % MOD + (2LL*l1*r1) % MOD) % MOD;
    };

    dfs(dfs, 0);
}

int count_ways(int L, int R) {
    // we need to propagate...
    update(0, 0, n-1, L-n, R-n);

    return dp[0][1];
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 4
• Subtask 5: 0 / 12
• Subtask 6: 0 / 27
• Subtask 7: 0 / 28
• Subtask 8: 0 / 11