Submission #1227143

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227143		brinton	Digital Circuit (IOI22_circuit)	C++20	2 / 100	3028 ms	7704 KiB

circuit

#include "circuit.h"
// #include "stub.cpp"
#include <bits/stdc++.h>
#define MOD 1000002022
using namespace std;

struct SEG{
  private:
  struct Node{
    long long sum,val;
    bool flip;
    Node(){}
    Node(long long isum){
      sum = isum,flip = false,val = 0;
    }
  };
  vector<Node> tree;
  vector<long long> mul;
  int N;
  void init(int l,int r,int idx){
    if(l == r){
      tree[idx] = Node(mul[l]);
      return;
    }
    int m = (l+r)/2;
    init(l,m,idx*2);
    init(m+1,r,idx*2+1);
    tree[idx] = Node(tree[idx*2].sum+tree[idx*2+1].sum);
  }
  void flip(int l,int r,int idx,int L,int R){
    if(l == L && r == R){
      tree[idx].val = tree[idx].sum-tree[idx].val;
      tree[idx].flip = !tree[idx].flip;
      return;
    }
    // push tag down
    if(tree[idx].flip){
      tree[idx*2].val = tree[idx*2].sum-tree[idx*2].val;
      tree[idx*2+1].val = tree[idx*2+1].sum-tree[idx*2+1].val;
      tree[idx*2].flip = !tree[idx*2].flip;
      tree[idx*2+1].flip = !tree[idx*2+1].flip;
      tree[idx].flip = false;
    }
    int m = (l+r)/2;
    if(R <= m){
      flip(l,m,idx*2,L,R);
    }else if(L >= m+1){
      flip(m+1,r,idx*2+1,L,R);
    }else{
      flip(l,m,idx*2,L,m);
      flip(m+1,r,idx*2+1,m+1,R);
    }

    tree[idx].val = tree[idx*2].val+tree[idx*2+1].val;// only val change;

  }
  public:
  SEG(){}
  SEG(vector<long long> imul){
    mul = imul;
    N = mul.size();
    tree.resize(4*N+5);
    init(0,N-1,1);
  }
  long long getAns(){
    return tree[1].val;
  }
  void flip(int l,int r){
    flip(0,N-1,1,l,r);
  }
};

vector<vector<int>> child;
vector<long long> tot;
vector<long long> mul;
int N,M;
vector<int> A;
SEG seg;
void init(int iN, int iM, vector<int> P, vector<int> iA) {
  N = iN,M = iM;
  A = iA;
  child.resize(N);
  for(int i = 1;i < P.size();i++){
    child[P[i]].push_back(i);
  }

  tot = vector<long long>(N+M,1);
  for(int i = N-1;i >= 0;i--){
    tot[i] = child[i].size();
    for(auto c:child[i]){
      tot[i] = tot[i]*tot[c]%MOD;
    }
  }

  mul.resize(M);
  function<void(int,long long)> dfs = [&](int cur,long long cval){
    if(cur >= N){
      mul[cur-N] = cval;
      return;
    }
    vector<long long> suf;
    for(auto nxt:child[cur]){
      suf.push_back(tot[nxt]);
    }
    for(int i = suf.size()-2;i >= 0;i--) suf[i] = suf[i]*suf[i+1]%MOD;
    long long pref = 1;
    for(int i = 0;i < child[cur].size();i++){
      int nxt = child[cur][i];
      if(i+1 < child[cur].size()) dfs(nxt,cval*pref%MOD*suf[i+1]%MOD);
      else dfs(nxt,cval*pref%MOD);
      pref = pref*tot[nxt]%MOD;
    }
  };
  dfs(0,1LL);
  for(int i = 0;i < M;i++)
  seg = SEG(mul);
  for(int i = 0;i < M;i++) if(A[i]) seg.flip(i,i);
  // for(auto &i:mul) cout << i << " ";cout << endl;
}

int count_ways(int L, int R) {
  L -= N, R -= N;
  seg.flip(L,R);
  return seg.getAns();
}
/*
62: precalculate size, multiply it, range flip
*/

• Subtask 1: 2 / 2
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 4
• Subtask 5: 0 / 12
• Subtask 6: 0 / 27
• Subtask 7: 0 / 28
• Subtask 8: 0 / 11