Submission #1236322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236322		rxlfd314	Digital Circuit (IOI22_circuit)	C++20	2 / 100	294 ms	18660 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

constexpr int mxN = 200005, MOD = 1000002022;
int N, M, tl[mxN], tr[mxN], lz[mxN];
vt<int> P, A;
vt<int> adj[mxN];
int dp0[mxN], dp1[mxN];
vt<vt<ari2>> dp[mxN];

void apply(const int i) {
  lz[i] ^= 1;
  swap(dp0[i], dp1[i]);
  if (i >= N)
    return;
  FOR(j, 1, size(adj[i]))
    FOR(k, 1, j)
      swap(dp[i][j][k][0], dp[i][j][k][1]);
}

void push(const int i) {
  if (!lz[i])
    return;
  for (const auto &j : adj[i])
    apply(j);
  lz[i] = 0;
}

void pull(const int i) {
  FOR(j, 0, size(adj[i]) - 1) {
    FOR(k, 0, j+1) {
      dp[i][j+1][k][1] = (k ? 1ll * dp[i][j][k-1][1] * dp1[adj[i][j]] % MOD : 0) + dp[i][j][k][1] * dp0[adj[i][j]] % MOD;
      dp[i][j+1][k][1] %= MOD;
      dp[i][j+1][k][0] = (k ? 1ll * dp[i][j][k-1][0] * dp0[adj[i][j]] % MOD : 0) + dp[i][j][k][0] * dp1[adj[i][j]] % MOD;
      dp[i][j+1][k][0] %= MOD;
    }
  }
  dp0[i] = dp1[i] = 0;
  FOR(x, 1, size(adj[i])) {
    dp0[i] += 1ll * dp[i][size(adj[i])][x][0] * x % MOD;
    dp0[i] %= MOD;
    dp1[i] += 1ll * dp[i][size(adj[i])][x][1] * x % MOD;
    dp1[i] %= MOD;
  }
}

void update(const int ql, const int qr, const int i) {
  if (tl[i] > qr || tr[i] < ql)
    return;
  if (ql <= tl[i] && tr[i] <= qr)
    apply(i);
  else {
    push(i);
    for (const auto &j : adj[i])
      update(ql, qr, j);
    pull(i);
  }
}

int count_ways(int L, int R) {
  update(L, R, 0);
  return dp1[0];
}

void init_dfs(const int i) {
  if (N <= i) {
    dp0[i] = !A[i-N];
    dp1[i] = A[i-N];
    tl[i] = tr[i] = i;
    return;
  }
  tl[i] = INT_MAX;
  tr[i] = -1;
  dp[i].assign(size(adj[i]) + 1, vt<ari2>(size(adj[i]) + 1));
  dp[i][0][0] = {1, 1};
  for (const auto &j : adj[i]) {
    init_dfs(j);
    tr[i] = max(tr[i], tr[j]);
    tl[i] = min(tl[i], tl[j]);
  }
  pull(i);
}

void init(int _N, int _M, vt<int> _P, vt<int> _A) {
  N = _N, M = _M, P = _P, A = _A;
  FOR(i, 1, N+M-1)
    adj[P[i]].push_back(i);
  init_dfs(0);
}

• 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