제출 #1315087

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1315087		Rares	Digital Circuit (IOI22_circuit)	C++20	100 / 100	382 ms	36028 KiB

circuit

#include <bits/stdc++.h>
using namespace std;

const int MAXN=2e5+10;
const int MOD=1000002022;

int c[MAXN],n,m,s[MAXN],a[MAXN];

vector <int> g[MAXN];

void dfs (int node){
    int aux=g[node].size();
    s[node]=max (1,aux);
    for (auto x:g[node]){
        dfs (x);
        s[node]=1LL*s[node]*s[x]%MOD;
    }
}

void solve (int node){

    vector <int> dpp(g[node].size ()),dps(g[node].size ());
    for (int i=0;i<g[node].size ();++i){
        int x=g[node][i];
        if (i==0) dpp[i]=s[x];
        else dpp[i]=1LL*dpp[i-1]*s[x]%MOD;
    }

    for (int i=g[node].size ()-1;i>=0;--i){
        int x=g[node][i];
        if (i==g[node].size ()-1) dps[i]=s[x];
        else dps[i]=1LL*dps[i+1]*s[x]%MOD;
    }

    for (int i=0;i<g[node].size ();++i){
        int crt=c[node],x=g[node][i];
        if (i!=0) crt=1LL*crt*dpp[i-1]%MOD;
        if (i!=g[node].size()-1) crt=1LL*crt*dps[i+1]%MOD;
        c[x]=crt;
        solve (x);
    }
}

struct AINT{
    int aint[4*MAXN],lazy[4*MAXN],sum[4*MAXN];

    void init (int node, int l, int r){

        if (l==r){
            sum[node]=c[l+n];
            if (a[l]) aint[node]=sum[node];
            else aint[node]=0;
            return;
        }

        int mij=(l+r)/2;
        init (2*node,l,mij);
        init (2*node+1,mij+1,r);

        sum[node]=(sum[2*node]+sum[2*node+1])%MOD;
        aint[node]=(aint[2*node]+aint[2*node+1])%MOD;
    }

    void lz (int node, int l, int r){
        if (lazy[node]==0) return;
        aint[node]=(sum[node]-aint[node]+MOD)%MOD;
        if (l!=r){
            lazy[2*node]^=lazy[node];
            lazy[2*node+1]^=lazy[node];
        }
        lazy[node]=0;
    }

    void update (int node, int l, int r, int ql, int qr){
        lz (node,l,r);
        if (r<ql or l>qr) return;
        if (ql<=l and r<=qr){
            lazy[node]^=1;
            lz (node,l,r);
            return;
        }
        int mij=(l+r)/2;
        update (2*node,l,mij,ql,qr);
        update (2*node+1,mij+1,r,ql,qr);
        aint[node]=(aint[2*node]+aint[2*node+1])%MOD;
    }

    void update (int l, int r){
        l-=n;
        r-=n;
        update (1,0,m-1,l,r);
    }
}v;

void init (int N, int M, vector <int> p, vector <int> A){
    n=N;
    m=M;
    for (int i=0;i<m;++i) a[i]=A[i];
    for (int i=1;i<p.size ();++i){
        g[p[i]].push_back (i);
    }

    dfs (0);

    c[0]=1;
    solve (0);

    v.init (1,0,m-1);
}

int count_ways (int l, int r){
    v.update (l,r);
    return v.aint[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