Submission #1213219

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213219		simona1230	Digital Circuit (IOI22_circuit)	C++20	7 / 100	3019 ms	9208 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
const int mod=1000002022;

int n,m;
vector<int> v[200001];
long long c[200001],c1[200001],c2[200001];
long long dp[200001][2];
int a[200001];

void dfs(int i)
{
    //cout<<i<<" in"<<endl;
    c[i]=v[i].size();
    if(c[i]==0)
    {
        c[i]=1;
        dp[i][a[i]]=1;
        dp[i][a[i]^1]=0;
        return;
    }
    dp[i][0]=dp[i][1]=0;

    for(int j=0;j<v[i].size();j++)
    {
        int nb=v[i][j];
        dfs(nb);
        c[i]*=c[nb];
        c[i]%=mod;
        c1[nb]=c2[nb]=c[nb];
        if(j!=0)c1[nb]*=c1[v[i][j-1]];
        c1[nb]%=mod;
        if(j!=v[i].size()-1)c2[nb]*=c2[v[i][j+1]];
        c2[nb]%=mod;
    }

    for(int j=0;j<v[i].size();j++)
    {
        int nb=v[i][j];
        int wo=1;
        if(j!=0)wo*=c1[v[i][j-1]];
        wo%=mod;
        if(j!=v[i].size()-1)wo*=c2[v[i][j+1]];
        wo%=mod;
        dp[i][0]+=dp[nb][0]*wo;
        dp[i][0]%=mod;
        dp[i][1]+=dp[nb][1]*wo;
        dp[i][1]%=mod;
    }
    //cout<<i<<" out"<<endl;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A)
{
    n=N;
    m=M;
    for(int i=1;i<P.size();i++)
        v[P[i]].push_back(i);
    for(int i=0;i<A.size();i++)
        a[n+i]=A[i];
    return;
}

int count_ways(int L, int R)
{
    for(int i=L;i<=R;i++)
        a[i]^=1;

    dfs(0);
    return dp[0][1];
}

• 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