Submission #1239529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239529		AlperenT_	Digital Circuit (IOI22_circuit)	C++20	100 / 100	370 ms	68380 KiB

circuit

#include "circuit.h"
#include <vector>
#include <bits/stdc++.h> 
#pragma GCC optimize("O3,unroll-loops") 
#pragma GCC target("avx2") 
#define pb push_back
#define F first
#define pii pair<int,int> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld double
#define int long long 
using namespace std ;
const int maxn = 1e6 + 10 , inf = 1e9+ 10 , mod = 1000002022 ;
int a[maxn] , n ,m , ans[maxn]; 
vector <int >G[maxn] ;
int sb[maxn] ;

int sm[4*maxn][2] , lz[4*maxn] ;

void bui(int p =1 ,int l =0 , int r =m-1){
  int mid = (l+r)/2 , pl = p<<1 , pr =p<<1|1 ;
  if(l == r){
    sm[p][a[l]^1] = ans[l]; 
    sm[p][a[l]] =0 ;
    lz[p] =0 ;
    return ;
  }
  bui(pl,l,mid);
  bui(pr,mid+1,r);
  sm[p][0] = (sm[pl][0] + sm[pr][0]) % mod ;
  sm[p][1] = (sm[pl][1] + sm[pr][1]) % mod ;
  lz[p] = 0;
}
void shi(int p){
  int  pl=p<<1, pr =p<<1|1 ;
  if(lz[p] == 1){
    lz[p] =0 ;
    swap(sm[pl][0] , sm[pl][1]) ;
    swap(sm[pr][0] , sm[pr][1]) ;
    lz[pl] ^= 1;
    lz[pr] ^= 1; 
  }
}
void upd(int le, int ri , int p =1 , int l =0 , int r = m-1){
  int mid = (l+r)/2 , pl=p<<1, pr =p<<1|1 ;
  if(le > r || l > ri)return; 
  if(le <= l && r <= ri){
    swap(sm[p][0] , sm[p][1]) ;
    lz[p] ^=1 ;
    return; 
  }
  shi(p) ;
  upd(le,ri,pl,l,mid);
  upd(le,ri,pr,mid+1,r);
  sm[p][0] = (sm[pl][0] + sm[pr][0]) % mod ;
  sm[p][1] = (sm[pl][1] + sm[pr][1]) % mod ;
  lz[p] = 0;
}

void dfs2(int v){
  sb[v] =1 ;
  if(v < n)sb[v] = sz(G[v]) ;
  for(int u : G[v]){
    dfs2(u) ;
    sb[v] = sb[v] * sb[u]  % mod ;
  }
}

void dfs(int v , int z =1 ){
  vector <int> pr  , sf;
  pr.pb(1);
  for(int u : G[v]){
    pr.pb(sb[u]) ;
    sf.pb(sb[u]) ;
  };
  sf.pb(1);
  rep(i , 1 ,sz(pr)-1){
    pr[i] = pr[i-1] * pr[i] % mod ;
  }
  per(i , sz(sf)-2 , 0){
    sf[i] = sf[i+1] * sf[i] % mod ;
  }
  if(v >= n)ans[v-n] = z ;
  int c =0  ; 
  for(int u : G[v]){
    dfs(u , z * pr[c] % mod * sf[c+1] % mod) ;
    c++ ;
  }

}
void init(int32_t N, int32_t M, std::vector<int32_t> P, std::vector<int32_t> A) {
    n = N ;
    m = M ; 
    rep(i ,1, n+m-1){
      G[P[i]].pb(i) ;
    }
    dfs2(0); 
    dfs(0) ;
    rep(i , 0 ,m-1)a[i] = A[i] ;
    bui(); 
}

int32_t count_ways(int32_t L, int32_t R) {
  upd(L-n , R-n) ;
  return sm[1][0] ;   
}

• 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