Submission #629138

#	Time	Username	Problem	Language	Result	Execution time	Memory
629138		kdh9949	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1304 ms	29456 KiB

circuit

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

using ll = long long;

const int SZ = 131072;
const ll MOD = ll(1e9) + 2022;
struct Seg {
  int l[2 * SZ];
  ll d[2 * SZ], w[2 * SZ];

  void i(int n, vector<int> a, vector<ll> v) {
    for(int i = 0; i < n; i++) w[i + SZ] = v[i];
    for(int i = 0; i < n; i++) if(a[i]) d[i + SZ] = v[i];
    for(int i = SZ - 1; i; i--) {
      d[i] = (d[2 * i] + d[2 * i + 1]) % MOD;
      w[i] = (w[2 * i] + w[2 * i + 1]) % MOD;
    }
  }

  void flp(int x) {
    d[x] = (w[x] + MOD - d[x]) % MOD;
    l[x] ^= 1;
  }

  void u(int s, int e, int x = 1, int p = 0, int q = SZ - 1) {
    if(e < p || q < s) return;
    if(s <= p && q <= e) {
      flp(x);
      return;
    }
    if(l[x]) { flp(2 * x); flp(2 * x + 1); l[x] = 0; }
    u(s, e, 2 * x, p, (p + q) / 2);
    u(s, e, 2 * x + 1, (p + q) / 2 + 1, q);
    d[x] = (d[2 * x] + d[2 * x + 1]) % MOD;
  }
} S;

int n;
void init(int N, int M, vector<int> P, vector<int> A) {
  n = N;
  vector<vector<int>> e(N);
  for(int i = 1; i < N + M; i++) e[P[i]].push_back(i);

  vector<ll> w(N);
  for(int i = N - 1; i; i--) {
    w[i] = e[i].size();
    for(int j : e[i]) if(j < N) (w[i] *= w[j]) %= MOD;
  }

  vector<ll> v(M);
  const function<void(int, ll)> f = [&](int x, ll t) {
    if(x >= N) {
      v[x - N] = t;
      return;
    }
    vector<ll> sf = {1};
    for(int i = int(e[x].size()) - 1; i; i--)
      sf.push_back(sf.back() * (e[x][i] < N ? w[e[x][i]] : 1) % MOD);
    ll pf = 1;
    for(int i : e[x]) {
      f(i, t * pf % MOD * sf.back() % MOD);
      if(i < N) (pf *= w[i]) %= MOD;
      sf.pop_back();
    }
  };
  f(0, 1);

  S.i(M, A, v);
}

int count_ways(int L, int R) {
  S.u(L - n, R - n);
  return S.d[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