Submission #856107

#	Time	Username	Problem	Language	Result	Execution time	Memory
856107		Urvuk3	Digital Circuit (IOI22_circuit)	C++17	100 / 100	764 ms	51600 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int INF=1e9;
const ll LINF=1e18;
#define fi first
#define se second
#define pii pair<int,int>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
#define endl "\n"
#define pb push_back

void PRINT(int x) {cerr << x;}
void PRINT(ll x) {cerr << x;}
void PRINT(double x) {cerr << x;}
void PRINT(char x) {cerr << '\'' << x << '\'';}
void PRINT(string x) {cerr << '\"' << x << '\"';}
void PRINT(bool x) {cerr << (x ? "true" : "false");}

template<typename T,typename V>
void PRINT(pair<T,V>& x){
    cerr<<"{";
    PRINT(x.fi);
    cerr<<",";
    PRINT(x.se);
    cerr<<"}";
}
template<typename T>
void PRINT(T &x){
    int id=0;
    cerr<<"{";
    for(auto _i:x){
        cerr<<(id++ ? "," : "");
        PRINT(_i);
    }
    cerr<<"}";
}
void _PRINT(){
    cerr<<"]\n";
}
template<typename Head,typename... Tail>
void _PRINT(Head h,Tail... t){
    PRINT(h);
    if(sizeof...(t)) cerr<<", ";
    _PRINT(t...);
}

#define Debug(x...) cerr<<"["<<#x<<"]=["; _PRINT(x)

const int mxN=2e5;
const ll MOD=1000002022;

vector<ll> contribute(mxN,1),sub(mxN,1);
vector<int> lazy(4*mxN),adj[mxN];
int N,M;

void Md(ll& x){
    if(x>=MOD) x%=MOD;
    if(x<0) x+=MOD;
}

struct Node{
    ll tmp,all;
}; vector<Node> seg(4*mxN);

Node Merge(Node& n1,Node& n2){
    Node ret={n1.tmp+n2.tmp,n1.all+n2.all};
    Md(ret.tmp); Md(ret.all);
    return ret;
}

void Propagate(int node,int l,int r){
    if(lazy[node]){
        seg[node].tmp=seg[node].all-seg[node].tmp; Md(seg[node].tmp);
        if(l<=r){
            lazy[2*node]^=1;
            lazy[2*node+1]^=1;
        }
        lazy[node]=0;
    }
}

void Build(int node,int l,int r,vector<int>& A){
    if(l==r){
        seg[node].tmp=(A[l] ? contribute[l+N] : 0);
        seg[node].all=contribute[l+N];
        return;
    }
    Build(2*node,l,mid,A); Build(2*node+1,mid+1,r,A);
    seg[node]=Merge(seg[2*node],seg[2*node+1]);
}

void Update(int node,int l,int r,int L,int R){
    if(l>r) return;
    Propagate(node,l,r);
    if(L>r || R<l) return;
    if(L<=l && r<=R){
        lazy[node]=1;
        Propagate(node,l,r);
        return;
    }
    Update(2*node,l,mid,L,R); Update(2*node+1,mid+1,r,L,R);
    seg[node]=Merge(seg[2*node],seg[2*node+1]);
}

void DfsSub(int node,int par){
    int c=0;
    for(int v:adj[node]){
        if(v!=par){
            DfsSub(v,node);
            sub[node]*=sub[v]; Md(sub[node]);
            c++;
        }
    }
    if(0<=node && node<N){
        sub[node]*=c; Md(sub[node]);
    }
}

void DfsCon(int node,int par){
    if(par!=-1){
        contribute[node]*=contribute[par]; Md(contribute[node]);
    }
    vector<ll> pref(sz(adj[node]),1),suf(sz(adj[node]),1);
    for(int i=0;i<sz(adj[node]);i++){
        int v=adj[node][i];
        if(i){
            pref[i]=pref[i-1]; Md(pref[i]);
        }
        if(v!=par){
            pref[i]*=sub[v]; Md(pref[i]);
        }
    }
    for(int i=sz(adj[node])-1;i>=0;i--){
        int v=adj[node][i];
        if(i!=sz(adj[node])-1){
            suf[i]=suf[i+1]; Md(suf[i]);
        }
        if(v!=par){
            suf[i]*=sub[v]; Md(suf[i]);
        }
    }
    for(int i=0;i<sz(adj[node]);i++){
        int v=adj[node][i];
        if(v!=par){
            if(i){
                contribute[v]*=pref[i-1]; Md(contribute[v]);
            }
            if(i<sz(adj[node])-1){
                contribute[v]*=suf[i+1]; Md(contribute[v]);
            }
        }
    }
    for(int v:adj[node]){
        if(v!=par){
            DfsCon(v,node);
        }
    }
}

void init(int N1, int M1, std::vector<int> P, std::vector<int> A) {
    N=N1,M=M1;
    for(int i=1;i<N+M;i++){
        adj[P[i]].pb(i);
    }
    DfsSub(0,-1);
    DfsCon(0,-1);
    Build(1,0,M-1,A);
}

int count_ways(int L, int R) {
    Update(1,0,M-1,L-N,R-N);
    return seg[1].tmp;
}

• 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