Submission #1236878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236878		countless	Digital Circuit (IOI22_circuit)	C++20	7 / 100	3044 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;
ll dp[MAXN][2];

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

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

int count_ways(int L, int R) {
    for (int i = L-n; i <= R-n; i++) {
        a[i] ^= 1;
    }

    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 + (2*l0*r0) % MOD) % MOD;
        dp[u][1] = ((l0*r1) % MOD + (l1*r0) % MOD + (2*l1*r1) % MOD) % MOD;
    };

    dfs(dfs, 0);

    return dp[0][1];
}

• Subtask 1: 0 / 2
• Subtask 2: 7 / 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