Submission #1032124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032124		aymanrs	Digital Circuit (IOI22_circuit)	C++17	100 / 100	753 ms	21196 KiB

circuit

#include "circuit.h"

#include <vector>
const int MOD = 1000002022;
using namespace std;
struct node {
  long long s, x = 1;
  vector<node*> l;
};
void dfs(node* n){
  if(n->l.empty()){
    n->s = 1;
  }else n->s = n->l.size();
  for(node* c : n->l){
    dfs(c);
    n->s = n->s*c->s%MOD;
  }
}
void dfx(node* n){
  if(n->l.empty()) return;
  long long x = n->x;
  for(node* c : n->l){
    c->x = c->x*x%MOD;
    x = (x*c->s)%MOD;
  }
  x = 1;
  for(int i = n->l.size()-1;i >= 0;i--){
    node*c = n->l[i];
    c->x = c->x * x %MOD;
    x = (x*c->s)%MOD;
    dfx(c);
  }
}
const int nx = 4e5+10;
int st[nx], su[nx];bool lz[nx] = {false};
int n;
int cons(int i, int l, int r, const vector<int>& A, node g[]){
  if(l==r){
    if(A[l-n]) st[i] = g[l].x;
    else st[i]=0;
    su[i]=g[l].x;
    return st[i];
  }
  int m = l+r>>1;
  st[i] = (cons(i<<1, l, m, A, g)+cons(i<<1|1, m+1, r, A, g))%MOD;
  su[i] = (su[i<<1]+su[i<<1|1])%MOD;
  return st[i];
}
void upd(int i, int l, int r, int a, int b){
  if(lz[i]){
    st[i] = (su[i]-st[i]+MOD)%MOD;
    if(l!=r){
      lz[i<<1] ^= 1;
      lz[i<<1|1] ^= 1;
    }
    lz[i]=false;
  }
  if(b < l || r < a) return;
  if(a <= l && r <= b){
    st[i] = (su[i]-st[i]+MOD)%MOD;
    if(l!=r){
      lz[i<<1] ^= 1;
      lz[i<<1|1] ^= 1;
    }
    return;
  }
  int m = l+r>>1;
  upd(i<<1, l, m, a, b);upd(i<<1|1, m+1, r, a, b);
  st[i] = (st[i<<1]+st[i<<1|1])%MOD;
}
int nm;
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
  node g[N+M];
  nm = N+M-1;
  n = N;
  for(int i = 1;i < N+M;i++){
    g[P[i]].l.push_back(&g[i]);
  }
  dfs(&g[0]);
  dfx(&g[0]);
  cons(1, N, N+M-1, A, g);
}
int count_ways(int L, int R) {
  upd(1, n, nm, L, R);
  return st[1];
}

Compilation message (stderr)

circuit.cpp: In function 'int cons(int, int, int, const std::vector<int>&, node*)':
circuit.cpp:44:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |   int m = l+r>>1;
      |           ~^~
circuit.cpp: In function 'void upd(int, int, int, int, int)':
circuit.cpp:67:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |   int m = l+r>>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