Submission #914590

#	Time	Username	Problem	Language	Result	Execution time	Memory
914590		cig32	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1177 ms	24208 KiB

circuit

#include "circuit.h"
#include "bits/stdc++.h"
using namespace std;
#define int long long

#include <vector>

const int MAXN = 2e5 + 12;
const int MOD = 1e9 + 2022;
int n, m;
vector<int> adj[MAXN];
int contrib[MAXN];
int ans;
int a[MAXN];
int lazy[MAXN];
int Y[MAXN];
const int S = 320;
int sum[S];
int state[S];
int tot[S];
void calc_y(int node) {
  Y[node] = adj[node].size();
  Y[node] = max(1ll, Y[node]);
  for(int x: adj[node]) {
    calc_y(x);
    Y[node] *= Y[x];
    Y[node] %= MOD;
  }
}
void propagate(int node) {
  for(int x: adj[node]) {
    lazy[x] *= lazy[node];
    lazy[x] %= MOD;
    propagate(x);
  }
}
void init(int32_t N, int32_t M, std::vector<int32_t> P, std::vector<int32_t> A) {
  for(int i=0; i<M; i++) contrib[i] = 1;
  for(int i=1; i<N+M; i++) adj[P[i]].push_back(i);
  for(int i=0; i<M; i++) a[i] = A[i];
  n = N;
  m = M;
  ans = 0;
  calc_y(0);
  for(int i=0; i<N+M; i++) lazy[i] = 1;
  for(int i=0; i<N; i++) {
    int len = adj[i].size();
    int pre[len], suf[len];
    for(int j=0; j<len; j++) {
      pre[j] = Y[adj[i][j]];
      suf[j] = Y[adj[i][j]];
    }
    for(int j=1; j<len; j++) {
      pre[j] *= pre[j-1];
      pre[j] %= MOD;
    }
    for(int j=len-2; j>=0; j--) {
      suf[j] *= suf[j+1];
      suf[j] %= MOD;
    }
    for(int j=0; j<len; j++) {
      if(j > 0) lazy[adj[i][j]] *= pre[j-1];
      lazy[adj[i][j]] %= MOD;
      if(j + 1 < len) lazy[adj[i][j]] *= suf[j+1];
      lazy[adj[i][j]] %= MOD;
    }
  }
  propagate(0);
  for(int i=0; i<N+M; i++) {
    contrib[i] = lazy[i];
  }
  for(int i=0; i<M; i++) {
    sum[i / S] += a[i] * contrib[i + N];
    sum[i / S] %= MOD;
    state[i / S] = 0;
    tot[i / S] += contrib[i + N];
    tot[i / S] %= MOD;
  }
  for(int i=N; i<N+M; i++) {
    if(a[i-N]) ans = (ans + contrib[i]) % MOD;
  }
}

int32_t count_ways(int32_t L, int32_t R) {
  L -= n;
  R -= n;
  if(R - L <= 2 * S) {
    for(int i=L; i<=R; i++) {
      int og = a[i] ^ state[i / S];
      a[i] ^= 1;
      ans += MOD - og * contrib[i + n];
      ans %= MOD;
      sum[i / S] += MOD - og * contrib[i + n];
      sum[i / S] %= MOD;
      og ^= 1;
      ans += og * contrib[i + n];
      ans %= MOD;
      sum[i / S] += og * contrib[i + n];
      sum[i / S] %= MOD;
    }
    return ans;
  }
  while(L % S != 0) {
    int i = L;
    int og = a[i] ^ state[i / S];
    a[i] ^= 1;
    ans += MOD - og * contrib[i + n];
    ans %= MOD;
    sum[i / S] += MOD - og * contrib[i + n];
    sum[i / S] %= MOD;
    og ^= 1;
    ans += og * contrib[i + n];
    ans %= MOD;
    sum[i / S] += og * contrib[i + n];
    sum[i / S] %= MOD;
    L++;
  }
  while(R % S != S - 1) {
    int i = R;
    int og = a[i] ^ state[i / S];
    a[i] ^= 1;
    ans += MOD - og * contrib[i + n];
    ans %= MOD;
    sum[i / S] += MOD - og * contrib[i + n];
    sum[i / S] %= MOD;
    og ^= 1;
    ans += og * contrib[i + n];
    ans %= MOD;
    sum[i / S] += og * contrib[i + n];
    sum[i / S] %= MOD;
    R--;
  }
  for(int i=L; i<=R; i+=S) {
    ans += MOD - sum[i / S];
    ans %= MOD;
    state[i / S] ^= 1;
    ans += MOD + tot[i / S] - sum[i / S];
    ans %= MOD;
    sum[i / S] = tot[i / S] - sum[i / S];
  }
  return ans;
}

• 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