Submission #1228841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228841		ericl23302	Digital Circuit (IOI22_circuit)	C++20	7 / 100	3049 ms	3732 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MOD = 1000002022;

// int n, m;
// vector<pair<ll, ll>> segTree(2e5 + 5, {0, 0});
// vector<bool> lazy(2e5 + 5, false);

// pair<ll, ll> merge(pair<ll, ll> a, pair<ll, ll> b) {
//     pair<ll, ll> res = {0, 0};
//     (res.first += (2 * a.first * b.first)) %= MOD;
//     (res.first += (a.first * b.second + a.second * b.first)) %= MOD;
//     (res.second += (a.first * b.second + a.second * b.first)) %= MOD;
//     (res.second += (2 * a.second * b.second)) %= MOD;
//     return res;
// }

// void push_down(int cur, int treeLeft, int treeRight) {
//     if (!lazy[cur]) return;
//     swap(segTree[cur].first, segTree[cur].second);
//     lazy[cur] = false;
//     if (treeLeft == treeRight) return;
//     lazy[cur * 2 + 1] = !lazy[cur * 2 + 1];
//     lazy[cur * 2 + 2] = !lazy[cur * 2 + 2];
// }

// void setup(int cur, int treeLeft, int treeRight, int pos, pair<ll, ll> val) {
//     if (pos < treeLeft || pos > treeRight) return;
//     if (treeLeft == treeRight) {
//         segTree[cur] = val;
//         return;
//     }
//     int mid = (treeLeft + treeRight) / 2;
//     setup(cur * 2 + 1, treeLeft, mid, pos, val);
//     setup(cur * 2 + 2, mid + 1, treeRight, pos, val);
//     segTree[cur] = merge(segTree[cur * 2 + 1], segTree[cur * 2 + 2]);
// }

// void update(int cur, int treeLeft, int treeRight, int qLeft, int qRight) {
//     push_down(cur, treeLeft, treeRight);
//     if (qRight < treeLeft || qLeft > treeRight) return;
//     if (treeLeft >= qLeft && treeRight <= qRight) {
//         lazy[cur] = true;
//         push_down(cur, treeLeft, treeRight);
//         return;
//     }
//     int mid = (treeLeft + treeRight) / 2;
//     update(cur * 2 + 1, treeLeft, mid, qLeft, qRight);
//     update(cur * 2 + 2, mid + 1, treeRight, qLeft, qRight);
//     segTree[cur] = merge(segTree[cur * 2 + 1], segTree[cur * 2 + 2]);
// }

// void init(int N, int M, std::vector<int> P, std::vector<int> A) {
//     n = N; 
//     m = M;
//     for (int i = 0; i < M; ++i) {
//         if (A[i]) setup(0, 1, M, i + 1, {0, 1});
//         else setup(0, 1, M, i + 1, {1, 0});
//     }
// }

// int count_ways(int L, int R) {
//     update(0, 1, m, L - n + 1, R - n + 1);
//     return segTree[0].second;
// }

int n, m;
vector<int> a;
vector<vector<int>> children;

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    n = N; 
    m = M;
    children.resize(N);
    for (int i = 1; i < N + M; ++i) children[P[i]].push_back(i);
    for (int &i : A) a.push_back(i);
}

int count_ways(int L, int R) {
    for (int i = L - n; i <= R - n; ++i) a[i] = 1 - a[i];
    vector<pair<ll, ll>> dp(n + m);
    for (int i = 0; i < m; ++i) {
        if (a[i]) dp[i + n] = {0, 1};
        else dp[i + n] = {1, 0};
    }

    for (int i = n - 1; i >= 0; --i) {
        auto &x = dp[children[i][0]], &y = dp[children[i][1]];
        (dp[i].first += (2 * x.first * y.first)) %= MOD;
        (dp[i].first += (x.first * y.second + x.second * y.first)) %= MOD;
        (dp[i].second += (x.first * y.second + x.second * y.first)) %= MOD;
        (dp[i].second += (2 * x.second * y.second)) %= MOD;
    }

    return dp[0].second;
}

• 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