Submission #1235111

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235111		guagua0407	Digital Circuit (IOI22_circuit)	C++20	100 / 100	384 ms	43460 KiB

circuit

#include "circuit.h"
//#include "stub.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define all(x) x.begin(),x.end()

namespace{
  const int mxn=2e5+5;
  const ll mod=(ll)1000002022;
  int n,m;
  vector<vector<int>> adj(mxn);
  vector<ll> tot(mxn);
  vector<int> a;
  vector<ll> co(mxn);
  void dfs(int v){
    if(v>=n){
      tot[v]=1;
      return;
    }
    tot[v]=(int)adj[v].size();
    for(auto u:adj[v]){
      dfs(u);
      tot[v]=tot[v]*tot[u]%mod;
    }
  }
  void dfs2(int v,ll val=1){
    if(v>=n){
      co[v-n]=val;
      return;
    }
    int sz=(int)adj[v].size();
    vector<ll> suf(sz+1);
    suf[sz]=1;
    for(int i=sz-1;i>=0;i--){
      suf[i]=suf[i+1]*tot[adj[v][i]]%mod;
    }
    ll pre=1;
    for(int i=0;i<sz;i++){
      int u=adj[v][i];
      dfs2(u,pre*suf[i+1]%mod*val%mod);
      pre=pre*tot[u]%mod;
    }
    //cout<<v<<' '<<ans<<'\n';
    return;
  }
  vector<ll> zero(mxn*4);
  vector<ll> one(mxn*4);
  vector<int> tag(mxn*4);
  void init(int l=0,int r=m-1,int v=1){
    if(l==r){
      if(a[l]) one[v]=co[l];
      else zero[v]=co[l];
      return;
    }
    int mid=(l+r)/2;
    init(l,mid,v*2);
    init(mid+1,r,v*2+1);
    zero[v]=(zero[v*2]+zero[v*2+1])%mod;
    one[v]=(one[v*2]+one[v*2+1])%mod;
  }
  void push(int v){
    if(tag[v]){
      swap(one[v*2],zero[v*2]);
      swap(one[v*2+1],zero[v*2+1]);
      tag[v*2]^=1;
      tag[v*2+1]^=1;
      tag[v]=0;
    }
  }
  void update(int tl,int tr,int l=0,int r=m-1,int v=1){
    if(r<tl or tr<l){
      return;
    }
    if(tl<=l and r<=tr){
      swap(zero[v],one[v]);
      tag[v]^=1;
      return;
    }
    push(v);
    int mid=(l+r)/2;
    update(tl,min(mid,tr),l,mid,v*2);
    update(max(mid+1,tl),tr,mid+1,r,v*2+1);
    zero[v]=(zero[v*2]+zero[v*2+1])%mod;
    one[v]=(one[v*2]+one[v*2+1])%mod;
  }
}

void init(int N ,int M, std::vector<int> P, std::vector<int> A) {
  n=N;
  m=M;
  a=A;
  for(int i=1;i<n+m;i++){
    adj[P[i]].push_back(i);
  }
  dfs(0);
  dfs2(0);
  init();
}

int count_ways(int L, int R) {
  update(L-n,R-n);
  return one[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