Submission #1213313

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213313		simona1230	Digital Circuit (IOI22_circuit)	C++20	100 / 100	397 ms	27920 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
const long long mod=1000002022;
const int maxn=100000*2+5;
int n,m;
vector<int> v[maxn];
long long c[maxn],all=1;

long long mult(long long x,long long p)
{
    if(p==1)return x;
    long long h=mult(x,p/2);
    if(p%2==0)return h*h%mod;
    return h*h%mod*x%mod;
}

int a[maxn];

void dfs(int i)
{
    c[i]=v[i].size();
    if(v[i].size()==0)c[i]=1;
    for(int j=0;j<v[i].size();j++)
    {
        int nb=v[i][j];
        dfs(nb);
        c[i]*=c[nb];
        c[i]%=mod;
    }
    all*=c[i];
    all%=mod;
    //cout<<i<<" "<<c[i]<<endl;
}

long long b[200001];
long long c1[200001],c2[200001];

void dfs0(int i,int h)
{
    if(v[i].size()==0)
    {
        //cout<<i<<" "<<h<<endl;
        b[i]=h;
    }

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

    for(int j=v[i].size()-1;j>=0;j--)
    {
        int nb=v[i][j];
        c2[nb]=c[nb];
        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];
        long long curr=h;
        if(j!=0)curr*=c1[v[i][j-1]];
        curr%=mod;
        if(j!=v[i].size()-1)curr*=c2[v[i][j+1]];
        curr%=mod;
        dfs0(nb,curr);
    }
}

int sum[4*maxn],sw[4*maxn],add[4*maxn];

void build(int i,int l,int r)
{
    if(l==r)
    {
        sum[i]=b[l];
        if(a[l])add[i]=b[l];
        sw[i]=0;
        return;
    }

    int md=(l+r)/2;
    build(i*2,l,md);
    build(i*2+1,md+1,r);
    sum[i]=sum[i*2]+sum[i*2+1];
    sw[i]=0;
    add[i]=add[i*2]+add[i*2+1];
    sum[i]%=mod;
    add[i]%=mod;
}

void pushsw(int i,int l,int r)
{
    if(sw[i]==0)return;

    add[i]=sum[i]-add[i];
    if(add[i]<0)add[i]+=mod;
    sw[i]=0;

    if(l!=r)
    {
        sw[i*2]^=1;
        sw[i*2+1]^=1;
    }
}

void update(int i,int l,int r,int ql,int qr)
{
    //cout<<i<<" "<<l<<" "<<r<<" "<<ql<<" "<<qr<<endl;
    pushsw(i,l,r);
    if(ql>qr)return;
    if(ql<=l&&r<=qr)
    {
        sw[i]^=1;
        pushsw(i,l,r);
        return;
    }

    int md=(l+r)/2;
    update(i*2,l,md,ql,min(qr,md));
    update(i*2+1,md+1,r,max(ql,md+1),qr);

    add[i]=add[i*2]+add[i*2+1];
    add[i]%=mod;
}

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];
        dfs(0);
        dfs0(0,1);
        build(1,n,n+m-1);
    return;
}

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

    long long ans=0;
    for(int i=n;i<=n+m-1;i++)
        if(a[i])ans=(ans+b[i])%mod;*/
    update(1,n,n+m-1,L,R);
    return add[1];
}

• 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