Submission #1193055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193055		vnm06	Digital Circuit (IOI22_circuit)	C++20	46 / 100	3090 ms	12292 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>

using namespace std;

const long long mod=1000002022;
const int MAXN=200005;

int n;
long long dp[MAXN];
vector<int> gr[MAXN];

void dfs(int v)
{
    int brs=gr[v].size();
    dp[v]=brs;
    if(!brs) dp[v]=1;
    for(int i=0; i<brs; i++)
    {
        dfs(gr[v][i]);
        dp[v]*=dp[gr[v][i]];
        dp[v]%=mod;
    }
}

long long tole[MAXN], tori[MAXN];
long long coef[MAXN];

void dfs_hp(int v)
{
    int brs=gr[v].size();
    if(!brs) return;
    if(brs==1)
    {
        coef[gr[v][0]]=1;
        dfs_hp(gr[v][0]);
        return;
    }
    tole[0]=dp[gr[v][0]];
    for(int i=1; i<brs; i++)
    {
        tole[i]=tole[i-1]*dp[gr[v][i]]%mod;
    }
    tori[brs-1]=dp[gr[v][brs-1]];
    for(int i=brs-2; i>=0; i--)
    {
        tori[i]=tori[i+1]*dp[gr[v][i]]%mod;
    }
    coef[gr[v][0]]=tori[1];
    coef[gr[v][brs-1]]=tole[brs-2];
    for(int i=1; i<brs-1; i++)
    {
        coef[gr[v][i]]=tole[i-1]*tori[i+1]%mod;
    }
    for(int i=0; i<brs; i++) dfs_hp(gr[v][i]);
}

long long pozv[MAXN];
long long st[MAXN];

void dfs_final(int v)
{
    int brs=gr[v].size();
    for(int i=0; i<brs; i++)
    {
        st[gr[v][i]]*=st[v];
        st[gr[v][i]]%=mod;
        dfs_final(gr[v][i]);
    }
}

void init(int N, int M, std::vector<int> P, std::vector<int> A)
{
    n=N+M;
    for(int i=1; i<N+M; i++)
    {
        gr[P[i]].push_back(i);
    }
    dfs(0);
    //for(int i=0; i<n; i++) cout<<dp[i]<<" ";
    //cout<<endl;
    dfs_hp(0);
    coef[0]=1;
    for(int i=0; i<N+M; i++) st[i]=coef[i];
    //for(int i=0; i<n; i++) cout<<st[i]<<" ";
    //cout<<endl;
    dfs_final(0);
    //for(int i=0; i<n; i++) cout<<st[i]<<" ";
    //cout<<endl;
    for(int i=0; i<M; i++) pozv[N+i]=A[i];
    //for(int i=0; i<n; i++) cout<<pozv[i]<<" ";
    //cout<<endl;
}

int count_ways(int L, int R)
{
    //cout<<L<<" "<<R<<endl;
    long long ans=0;
    for(int i=L; i<=R; i++) pozv[i]^=1;
    for(int i=0; i<n; i++)
    {
        //cout<<pozv[i]<<" "<<st[i]<<endl;
        ans+=pozv[i]*st[i];
    }
    return 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