Submission #1125265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125265		imarn	Digital Circuit (IOI22_circuit)	C++20	100 / 100	527 ms	42400 KiB

circuit

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
using namespace std;
const int mxn=2e5+5;
const ll inf=1000002022;
vector<int>g[mxn],a;
ll mul[mxn]{0};
ll dp[2][mxn]{0};
int n,m;
ll t[2][4*mxn]{0};
int lz[4*mxn]{0};
void build(int i,int l,int r){
    lz[i]=0;
    if(l==r){
        t[1][i]=dp[a[l]][l],t[0][i]=dp[a[l]^1][l];
        return;
    }
    int m=(l+r)>>1;
    build(2*i,l,m);build(2*i+1,m+1,r);
    t[0][i]=(t[0][2*i]+t[0][2*i+1])%inf;
    t[1][i]=(t[1][2*i]+t[1][2*i+1])%inf;
}
void push(int i,int l,int r){
    if(lz[i]==0)return;
    if(lz[i]&1)swap(t[0][i],t[1][i]);
    if(l<r)lz[2*i]+=lz[i],lz[2*i+1]+=lz[i];
    lz[i]=0;
}
void update(int i,int l,int r,int tl,int tr){
    push(i,l,r);
    if(r<tl||l>tr)return;
    if(r<=tr&&l>=tl){
        lz[i]+=1;push(i,l,r);return;
    }int m=(l+r)>>1;
    update(2*i,l,m,tl,tr);update(2*i+1,m+1,r,tl,tr);
    t[0][i]=(t[0][2*i]+t[0][2*i+1])%inf;
    t[1][i]=(t[1][2*i]+t[1][2*i+1])%inf;
}
void dfs1(int u){
    mul[u]=(ll)g[u].size();
    if(g[u].size()==0)mul[u]=1;
    for(auto v:g[u]){
        dfs1(v);
        mul[u]*=mul[v];mul[u]%=inf;
    }
}
void dfs2(int u,ll x){
    vector<ll>l,r;
    for(auto v:g[u]){
        l.pb(mul[v]);
    }r=l;
    if(u>=n)dp[1][u-n]=x;
    for(int i=1;i<l.size();i++)l[i]*=l[i-1],l[i]%=inf;
    for(int i=(int)r.size()-2;i>=0;i--)r[i]*=r[i+1],r[i]%=inf;
    for(int j=0;j<g[u].size();j++){
        ll rs=1;
        if(j>0)rs*=l[j-1],rs%=inf;
        if(j+1<g[u].size())rs*=r[j+1],rs%=inf;
        dfs2(g[u][j],(rs*x)%inf);
    }
}
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++)g[P[i]].pb(i);a=A;
    dfs1(0);dfs2(0,1);
    //for(int i=0;i<n;i++)cout<<mul[i]<<' ';cout<<'\n';
    //for(int i=0;i<m;i++)cout<<dp[0][i]<<' '<<dp[1][i]<<'\n';
    build(1,0,m-1);
}

int count_ways(int L, int R) {
    update(1,0,m-1,L-n,R-n);
    return (t[1][1]%inf+inf)%inf;
}

• 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