Submission #1058416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058416		Huseyn123	디지털 회로 (IOI22_circuit)	C++17	100 / 100	744 ms	35812 KiB

circuit

#include <bits/stdc++.h> 
#include "circuit.h"
#define MAX 200001
using namespace std; 
typedef long long ll;
int n,m; 
const int mod=1000002022;
vector<vector<int>> g;
long long dp[MAX],dp1[MAX];
void dfs(int v){
  if(v>=n){
    dp[v]=1; 
    return;
  }
  dp[v]=(int)g[v].size();
  for(auto x:g[v]){
    dfs(x);
    dp[v]*=dp[x];
    dp[v]%=mod;
  }
}
void dfs1(int v){
  if(v>=n){
    return; 
  }
  int sz=(int)g[v].size(); 
  vector<ll> pref(sz),suf(sz);
  for(int i=0;i<sz;i++){
    pref[i]=dp[g[v][i]];
    if(i){
      pref[i]*=pref[i-1];
      pref[i]%=mod;
    }
  }
  for(int i=sz-1;i>=0;i--){
    suf[i]=dp[g[v][i]];
    if(i!=sz-1){
      suf[i]*=suf[i+1];
      suf[i]%=mod;
    }
  }
  for(int i=0;i<sz;i++){
    int pr,sf; 
    pr=sf=1;
    if(i){
      pr=pref[i-1];
    }
    if(i!=sz-1){
      sf=suf[i+1];
    }
    dp1[g[v][i]]=dp1[v];
    dp1[g[v][i]]*=pr;
    dp1[g[v][i]]%=mod; 
    dp1[g[v][i]]*=sf;
    dp1[g[v][i]]%=mod; 
    dfs1(g[v][i]);
  }
}
ll sm(ll x,ll y){
  ll res=(x+y)%mod; 
  if(res<0){
    res+=mod;
  }
  return res;
}
ll ml(ll x,ll y){
  ll res=(x*y)%mod; 
  if(res<0){
    res+=mod;
  }
  return res; 
}
struct segtree{
    vector<ll> sums;
    vector<ll> lazy;
    int size;
    void init(int n){
        size=1;
        while(size<n){
            size*=2;
        }
        sums.assign(2*size,0LL);
        lazy.assign(2*size,1LL);
    }
    void build(int x,int lx,int rx,vector<int> &a){
        if(rx-lx==1){
            if(lx<(int)a.size()){
                sums[x]=a[lx];
            }
            return;
        }
        int m=(lx+rx)/2;
        build(2*x+1,lx,m,a);
        build(2*x+2,m,rx,a);
        sums[x]=sm(sums[2*x+1],sums[2*x+2]);
    }
    void build(vector<int> &a){
        build(0,0,size,a);
    }
    void propogate(int x,int lx,int rx){
        if(rx-lx==1){
            return;
        }
        sums[2*x+1]=ml(sums[2*x+1],lazy[x]);
        sums[2*x+2]=ml(sums[2*x+2],lazy[x]);
        lazy[2*x+1]=ml(lazy[2*x+1],lazy[x]);
        lazy[2*x+2]=ml(lazy[2*x+2],lazy[x]);
        lazy[x]=1;
    }
    void upd(int x,int lx,int rx,int l,int r,int v){
        propogate(x,lx,rx);
        if(rx<=l || lx>=r){
            return;
        }
        if(lx>=l && rx<=r){
            sums[x]=ml(sums[x],v);
            lazy[x]=ml(lazy[x],v);
            return;
        }
        int m=(lx+rx)/2;
        upd(2*x+1,lx,m,l,r,v);
        upd(2*x+2,m,rx,l,r,v);
        sums[x]=sm(sums[2*x+1],sums[2*x+2]);
    }
    void upd(int l,int r,int v){
        return upd(0,0,size,l,r,v);
    }
    ll get(int x,int lx,int rx,int l,int r){
        propogate(x,lx,rx);
        if(rx<=l || lx>=r){
            return 0;
        }
        if(lx>=l && rx<=r){
            return sums[x];
        }
        int m=(lx+rx)/2;
        ll s1,s2;
        s1=get(2*x+1,lx,m,l,r);
        s2=get(2*x+2,m,rx,l,r);
        return sm(s1,s2);
    }
    ll get(int l,int r){
        return get(0,0,size,l,r);
    }
};
segtree st;
ll res=0;
void init(int N, int M, vector<int> P, vector<int> A) {
  n=N; 
  m=M; 
  g.resize(n+m);
  for(int i=1;i<n+m;i++){
    g[P[i]].push_back(i);
  }
  dfs(0);
  dp1[0]=1;
  dfs1(0);
  st.init(m);
  vector<int> b;
  for(int i=0;i<m;i++){
    if(A[i]){
      res=sm(res,dp1[n+i]);
      b.push_back(-dp1[n+i]);
    }
    else{
      b.push_back(dp1[n+i]);
    }
  }
  st.build(b);
}
int count_ways(int L, int R) {
  res=sm(res,st.get(L-n,R-n+1));
  st.upd(L-n,R-n+1,-1);
  return res;
}

• 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