Submission #1193073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193073		vnm06	Digital Circuit (IOI22_circuit)	C++20	100 / 100	359 ms	33148 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]);
    }
}

long long pref[MAXN];

long long sums[4*MAXN];
long long segm_v[4*MAXN];
int lazy[4*MAXN];

void build_tree(int v, int le, int ri)
{
    if(le==ri)
    {
        sums[v]=pref[le];
        if(le) sums[v]-=pref[le-1];
        return;
    }
    int mid=(le+ri)/2;
    build_tree(2*v, le, mid);
    build_tree(2*v+1, mid+1, ri);
    sums[v]=sums[2*v]+sums[2*v+1];
}

void push_lazy(int v, int le, int ri)
{
    if(!lazy[v]) return;
    lazy[v]=0;
    segm_v[v]=sums[v]-segm_v[v];
    if(le!=ri)
    {
        lazy[2*v]^=1;
        lazy[2*v+1]^=1;
    }
}

void update_tree(int v, int le, int ri, int be, int en)
{
    push_lazy(v, le, ri);
    if(le>en || ri<be) return;
    if(be<=le && ri<=en)
    {
        lazy[v]=1;
        push_lazy(v, le, ri);
        return;
    }
    int mid=(le+ri)/2;
    update_tree(2*v, le, mid, be, en);
    update_tree(2*v+1, mid+1, ri, be, en);
    segm_v[v]=segm_v[2*v]+segm_v[2*v+1];
}

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);
    dfs_hp(0);
    coef[0]=1;
    for(int i=0; i<N+M; i++) st[i]=coef[i];
    dfs_final(0);

    pref[0]=st[0];
    for(int i=1; i<n; i++) pref[i]=pref[i-1]+st[i];
    build_tree(1, 0, n-1);

    for(int i=0; i<M; i++)
    {
        if(A[i]) update_tree(1, 0, n-1, N+i, N+i);
    }
}

int count_ways(int L, int R)
{
    update_tree(1, 0, n-1, L, R);
    return segm_v[1]%mod;
}

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