Submission #1146183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146183		Ludissey	Digital Circuit (IOI22_circuit)	C++17	2 / 100	3026 ms	5824 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define int long long
using namespace std;

int N,M;
const int MOD=1e9+2022;

vector<vector<int>> child;
vector<int> p;
vector<vector<bool>> toChange;
vector<int> state;
vector<int> alp; //all possiblities
vector<int> on;

void dfs(int x){
    for (auto u : child[x]) dfs(u);
    if(x>=N) {
        alp[x]=1;
        on[x]=state[x];
        return;
    }
    alp[x]=1;
    vector<int> rprfx(sz(child[x])+1);
    rprfx[sz(child[x])]=1;
    for (int i=sz(child[x])-1; i>=0; i--)
    {
        rprfx[i]=(rprfx[i+1]*alp[child[x][i]])%MOD;
    }
    int c=1;
    on[x]=0;
    for (int i=0; i<sz(child[x]); i++){
        int u=child[x][i];
        on[x]=(on[x]+(on[u]*(c*rprfx[i+1])))%MOD;
        c=(c*alp[u])%MOD;
    }
    alp[x]=(sz(child[x])*alp[x])%MOD;
    return;
}

void init(signed n, signed m, std::vector<signed> P, std::vector<signed> A) {
    N=n; M=m;
    p.resize(N+M);
    alp.resize(N+M,0);
    on.resize(N+M,0);
    for (int i = 0; i < N+M; i++) p[i]=P[i];
    child.resize(N+M); state.resize(N+M);
    for (int i = 1; i < N+M; i++) child[P[i]].push_back(i);
    for (int i = N; i < N+M; i++) state[i] = A[i-N];
}

signed count_ways(signed L, signed R) {
    for (int i = L; i <= R; i++) state[i] = 1-state[i];
    for (int i = 0; i < N; i++)
    {
        on[i]=0;
        alp[i]=1;
    }
    dfs(0);
    return on[0];
}

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