Submission #1235564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235564		Muhammad_Aneeq	Digital Circuit (IOI22_circuit)	C++17	4 / 100	769 ms	11772 KiB

circuit

#include "circuit.h"
#include <vector>
#include <iostream>
using namespace std;
#define ll long long
int const NPM=2e5+10,mod=1000002022;
vector<int>nei[NPM]={};
long long dp[NPM][2]={};
long long ways[2][NPM]={};
bool swp[NPM]={};
int P[NPM]={};
int l[NPM],r[NPM];
bool st[NPM]={};
int n,m;
long long mul(ll a,ll b)
{
    return (a*b)%mod;
}
long long add(ll a,ll b)
{
    return (a+b)%mod;
}
void comp(int u)
{
    int sz=nei[u].size();
    for (int i=1;i<=sz;i++)
        ways[0][i]=0;
    ways[0][0]=1;
    for (auto i:nei[u])
    {
        for (auto j:{0,1})
        {
            for (int k=sz;k>=j;k--)
                ways[1][k]=add(ways[1][k],mul(ways[0][k-j],dp[i][j]));
        }
        for (int k=0;k<=sz;k++)
        {
            ways[0][k]=ways[1][k];
            ways[1][k]=0;
        }
    }
    dp[u][1]=0;
    dp[u][0]=0;
    for (int i=0;i<=sz;i++)
    {
        dp[u][1]=add(dp[u][1],mul(ways[0][i],i));
        dp[u][0]=add(dp[u][0],mul(ways[0][i],(sz-i)));
    }
}
void dfs(int u)
{
    if (u>=n)
    {
        dp[u][st[u]]=1;
        dp[u][1-st[u]]=0;
        l[u]=r[u]=u;
        return;
    }
    l[u]=NPM,r[u]=0;
    for (auto i:nei[u])
    {
        dfs(i);
        l[u]=min(l[i],l[u]);
        r[u]=max(r[i],r[u]);
    }
    comp(u);
    
    // cout<<u<<' '<<dp[u][0]<<' '<<dp[u][1]<<endl;
}
void upd(int u,int L,int R)
{
    if (l[u]>R||r[u]<L)
        return ;
    if (swp[u])
    {
        swap(dp[u][0],dp[u][1]);
        for (auto j:nei[u])
            swp[j]^=1;
        swp[u]=0;
    }
    if (l[u]>=L&&r[u]<=R)
    {
        swap(dp[u][0],dp[u][1]);
        for (auto j:nei[u])
            swp[j]^=1;
        swp[u]=0;
        return;
    }
    for (auto j:nei[u])
        upd(j,L,R);
    comp(u);
}
void init(int N, int M, vector<int> P, vector<int> A) 
{
    n=N;
    m=M;
    for (int i=1;i<n+m;i++)
        nei[P[i]].push_back(i);
    for (int i=n;i<n+m;i++)
        st[i]=A[i-n];
    dfs(0);
}
int count_ways(int L, int R) 
{
    for (int i=L;i<=R;i++)
        st[i]^=1;
    upd(0,L,R);
    return dp[0][1];
}

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