Submission #1247465

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247465		erering	Digital Circuit (IOI22_circuit)	C++20	2 / 100	47 ms	64912 KiB

circuit

#include <bits/stdc++.h>
#include "circuit.h"
using namespace std;
#define pb push_back
#define ll long long
const ll MAXN=2000+5,MOD=1000002022;
ll n,m,cnt[MAXN],am[MAXN],suff[MAXN][MAXN];
vector<int> ch[MAXN];
ll dp[MAXN],prod[MAXN],num[MAXN][MAXN];
bool pos[MAXN];
//dp[i] ammount of ways to make i black. prod[i] how many ways to assign parameters in i subtree
//num[i] how many ways such i of its threshold children are black
void dfs(int node){
    prod[node]=1;
    int seen=0;
    num[node][0]=1;
    for(auto i:ch[node]){
        if(i<n){
            dfs(i);
            prod[node]*=prod[i]*am[i]%MOD;
            prod[node]%=MOD;
            if(!pos[i])continue;
            seen++;
            for(int j=seen;j>0;j--){
                num[node][j]+=num[node][j-1]*dp[i]%MOD; num[node][j]%=MOD;
            }
        }
    }
    for(int i=seen;i>0;i--)suff[node][i]=(num[node][i]+suff[node][i+1])%MOD;
    for(int i=1;i<=am[node];i++){
        if(cnt[node]>=i){
           // if(node==2)cout<<"HEE "<<cnt[node]<<' '<<i<<endl;
            pos[node]=1;
            dp[node]+=prod[node]; dp[node]%=MOD;
            continue;
        }
        int req=i-cnt[node];
        if(req>seen)continue;
        pos[node]=1;
        dp[node]+=suff[node][req]; dp[node]%=MOD;
    }
  //  cout<<node<<' '<<dp[node]<<endl;
}
vector<int> a,p;
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    for(int i=0;i<MAXN;i++){
        cnt[i]=0; am[i]=0; ch[i].clear(); dp[i]=0; pos[i]=0;
        for(int j=0;j<MAXN;j++){
            suff[i][j]=0;
            num[i][j]=0;
        }
    }
    p=P;
    a=A;
    n=N; m=M;
    for(int i=1;i<P.size();i++){
        ch[P[i]].pb(i);
        if(i>=n && A[i-N])cnt[P[i]]++;
        am[P[i]]++;
    }
  //  cout<<"bruv"<<cnt[2]<<endl;
}

int count_ways(int L, int R) {
    for(int i=L-n;i<=R-n;i++)a[i]^=1;
    init(n,m,p,a);
    dfs(0);
    return dp[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