Submission #632419

#	Time	Username	Problem	Language	Result	Execution time	Memory
632419		skittles1412	Digital Circuit (IOI22_circuit)	C++17	46 / 100	3084 ms	10844 KiB

circuit

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

const int maxn = 2e5 + 5;
const long mod = 1e9 + 2022;

int n;
vector<int> arr, graph[maxn];
long ways[maxn], contrib[maxn];

void pdfs(int u) {
    ways[u] = 1;
    for (auto& v : graph[u]) {
        pdfs(v);
        ways[u] = (ways[u] * ways[v]) % mod;
    }
    if (sz(graph[u])) {
        ways[u] = (ways[u] * sz(graph[u])) % mod;
    }
    dbg(u, ways[u]);
}

void dfs(int u, long x = 1) {
    int m = sz(graph[u]);
    if (!m) {
        dbg(u, x);
        contrib[u] = x;
        return;
    }
    long psum[m + 1], ssum[m + 1];
    psum[0] = ssum[m] = 1;
    for (int i = 0; i < m; i++) {
        psum[i + 1] = (psum[i] * ways[graph[u][i]]) % mod;
    }
    for (int i = m - 1; i >= 0; i--) {
        ssum[i] = (ssum[i + 1] * ways[graph[u][i]]) % mod;
    }
    for (int i = 0; i < m; i++) {
        dfs(graph[u][i], x * psum[i] % mod * ssum[i + 1] % mod);
    }
}

void init(int _n, int m, vector<int> p, vector<int> _arr) {
    n = _n;
    arr = _arr;
    for (int i = 1; i < n + m; i++) {
        graph[p[i]].push_back(i);
    }
    pdfs(0);
    dfs(0);
    copy(contrib + n, contrib + n + m, contrib);
}

int count_ways(int l, int r) {
    l -= n;
    r -= n;
    for (int i = l; i <= r; i++) {
        arr[i] ^= 1;
    }
    long ans = 0;
    for (int i = 0; i < sz(arr); i++) {
        ans += arr[i] * contrib[i];
    }
    return int(ans % mod);
}

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