Submission #628057

#	Time	Username	Problem	Language	Result	Execution time	Memory
628057		czhang2718	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1211 ms	36856 KiB

circuit

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;

const int mod=1e9+2022;
const int N=2e5;
int n, m, q;
vector<int> adj[N];
int p[N];
int a[N];
int sum[4*N], con[4*N], c[N];
ll prod[N];

int add(int a, int b){
    return ((a+mod)%mod+(b+mod)%mod)%mod;
}

void add2(int &a, int b){
    a=add(a,b);
}

int mult(ll a, ll b){
    return (a*b)%mod;
}

void mult2(ll &a, ll b){
    a=mult(a,b);
}

void dfs(int x){
    prod[x]=x<n?adj[x].size():1;
    for(int k:adj[x]){
        dfs(k);
        mult2(prod[x], prod[k]);
    }
}

void dfs2(int x){
    int p=adj[x].size();
    vector<ll> pre(p), suf(p);
    for(int i=0; i<p; i++){
        int k=adj[x][i];
        pre[i]=suf[i]=prod[k];
    }
    for(int i=1; i<p; i++){
        mult2(pre[i], pre[i-1]);
    }
    for(int i=p-2; i>=0; i--){
        mult2(suf[i], suf[i+1]);
    }

    for(int i=0; i<p; i++){
        int k=adj[x][i];
        c[k]=mult(c[x], mult(i?pre[i-1]:1, i<p-1?suf[i+1]:1));
        dfs2(k);
    }
}

short lazy[4*N];

void build(int x, int lx, int rx){
    if(rx-lx==1){
        con[x]=a[lx]?c[lx+n]:0;
        // cout << "c[" << lx+n << "] " << c[lx+n] << "\n";
        sum[x]=c[lx+n];
        return;
    }
    int m=(lx+rx)/2;
    build(2*x+1, lx, m);
    build(2*x+2, m, rx);
    con[x]=add(con[2*x+1], con[2*x+2]);
    sum[x]=add(sum[2*x+1], sum[2*x+2]);
}

void push(int x, int lx, int rx){
    if(rx-lx==1 || !lazy[x]) return;
    for(int y=2*x+1; y<=2*x+2; y++){
        con[y]=add(sum[y], -con[y]);
        lazy[y]^=1;
    }
    lazy[x]=0;
}

void tog(int l, int r, int x=0, int lx=0, int rx=m){
    push(x, lx, rx);
    if(lx>=r || rx<=l) return;
    if(lx>=l && rx<=r){
        con[x]=add(sum[x], -con[x]);
        lazy[x]=1;
        return;
    }
    int m=(lx+rx)/2;
    tog(l, r, 2*x+1, lx, m);
    tog(l, r, 2*x+2, m, rx);
    con[x]=add(con[2*x+1], con[2*x+2]);
}

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

  dfs(0);
  c[0]=1;
  dfs2(0);
  build(0, 0, m);
}

int count_ways(int l, int r) {
  l-=n; r-=n;
  tog(l, r+1);
  return con[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