Submission #966091

#	Time	Username	Problem	Language	Result	Execution time	Memory
966091		bachhoangxuan	Digital Circuit (IOI22_circuit)	C++17	100 / 100	746 ms	29076 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5+5;
const int mod = 1e9+2022;
int N,M,sz[maxn],suf[maxn],dp[maxn];
vector<int> A;
vector<int> edge[maxn];

struct node{
    int lazy=0;
    int total[2];
    node(){
        memset(total,0,sizeof(total));
    }
    friend node operator+(node a,node b){
        node res;
        for(int i=0;i<=1;i++) res.total[i]=(a.total[i]+b.total[i])%mod;
        return res;
    }
}tree[2*maxn];

void build(int l,int r,int id){
    if(l==r){
        tree[id].total[A[l]]=dp[N+l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,id<<1);build(mid+1,r,id<<1|1);
    tree[id]=tree[id<<1]+tree[id<<1|1];
}

void getnew(int id){
    tree[id].lazy^=1;
    swap(tree[id].total[0],tree[id].total[1]);
}
void pushdown(int id){
    if(tree[id].lazy){
        getnew(id<<1);
        getnew(id<<1|1);
        tree[id].lazy=0;
    }
}
void update(int l,int r,int id,int tl,int tr){
    if(tr<l || r<tl) return;
    if(tl<=l && r<=tr){
        getnew(id);
        return;
    }
    pushdown(id);
    int mid=(l+r)>>1;
    update(l,mid,id<<1,tl,tr);update(mid+1,r,id<<1|1,tl,tr);
    tree[id]=tree[id<<1]+tree[id<<1|1];
}

void init(int _N, int _M, vector<int> P, vector<int> _A) {
    N=_N;M=_M;A=_A;
    for(int i=1;i<N+M;i++){
        edge[P[i]].push_back(i);
        sz[P[i]]++;
    }
    function<void(int)> pre_dfs = [&](int u){
        dp[u]=max(sz[u],1);
        for(int v:edge[u]) pre_dfs(v),dp[u]=1LL*dp[u]*dp[v]%mod;
        //cout << "dp " << u << ' ' << dp[u] << '\n';
    };
    pre_dfs(0);
    function<void(int)> dfs = [&](int u){
        int cur=1;
        for(int i=(int)edge[u].size()-1;i>=0;i--){
            int v=edge[u][i];suf[v]=cur;
            cur=1LL*cur*dp[v]%mod;
        }
        cur=1;
        for(int v:edge[u]){
            int cc=dp[v];
            dp[v]=1LL*cur*suf[v]%mod*dp[u]%mod;
            dfs(v);cur=1LL*cur*cc%mod;
        }
    };
    dp[0]=1;dfs(0);
    //for(int i=0;i<N+M;i++) cout << dp[i] << ' ';
    //cout << '\n';
    build(0,M-1,1);
}

int count_ways(int L, int R) {
    update(0,M-1,1,L-N,R-N);
    return tree[1].total[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