Submission #1264929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264929		silentloop	Digital Circuit (IOI22_circuit)	C++20	11 / 100	3048 ms	2162688 KiB

circuit

#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;

const int MAXN = 2e5 + 1;
const int MOD = 1000002022;
vector<ll> grafo[MAXN];

ll val[MAXN], p[MAXN];

ll n, m, tot = 0;
pair<ll, ll> memo[MAXN];

pair<ll, ll> dfs(ll nod) // fr: posibilidades activo, se: posibilidades apagado
{
  if (nod >= n)
  {
    memo[nod]={val[nod], !val[nod]};
    return memo[nod];
  }
  pair<ll, ll> cant = {0, 0}, iz = dfs(grafo[nod][0]), der = dfs(grafo[nod][1]);
  cant.fr = (2ll * (iz.fr * der.fr) % MOD) % MOD;     // los dos en 1 (*2 pq se puede dejar en 1 con al menos 1 activo y con al menos 2 activos)
  cant.fr = (cant.fr + (iz.fr * der.se) % MOD) % MOD; // solo el de la izquierda activo
  cant.fr = (cant.fr + (der.fr * iz.se) % MOD) % MOD; // solo el de la derecha activo
  cant.se = (2ll * (iz.se * der.se) % MOD) % MOD;     // los 2 apagados
  cant.se = (cant.se + (iz.fr * der.se) % MOD) % MOD; // solo 1 activo con al menos 2 activos
  cant.se = (cant.se + (iz.se * der.fr) % MOD) % MOD; // solo 1 activo con al menos 2 activos
  memo[nod] = cant;
  return cant;
}

void calc()
{
  pair<ll, ll> a = dfs(0);
  tot = a.fr;
}

void init(int N, int M, std::vector<int> P, std::vector<int> A)
{
  ll i;
  p[0] = -1;
  for (i = 1; i < sz(P); i++)
  {
    p[i] = P[i];
    grafo[P[i]].pb(i);
  }
  for (i = 0; i < sz(A); i++)
    val[i + N] = A[i];
  n = N;
  m = M;
  calc();
}

void update(ll x)
{
  if (x == -1)
    return;
  pair<ll, ll> cant = {0, 0}, iz = memo[grafo[x][0]], der = memo[grafo[x][1]];
  cant.fr = (2ll * (iz.fr * der.fr) % MOD) % MOD;     // los dos en 1 (*2 pq se puede dejar en 1 con al menos 1 activo y con al menos 2 activos)
  cant.fr = (cant.fr + (iz.fr * der.se) % MOD) % MOD; // solo el de la izquierda activo
  cant.fr = (cant.fr + (der.fr * iz.se) % MOD) % MOD; // solo el de la derecha activo
  cant.se = (2ll * (iz.se * der.se) % MOD) % MOD;     // los 2 apagados
  cant.se = (cant.se + (iz.fr * der.se) % MOD) % MOD; // solo 1 activo con al menos 2 activos
  cant.se = (cant.se + (iz.se * der.fr) % MOD) % MOD; // solo 1 activo con al menos 2 activos
  memo[x] = cant;
  update(p[x]);
}

int count_ways(int L, int R)
{
  ll i;
  for(i=L; i<=R; i++)
  {
    val[i] = !val[i];
    memo[i]={val[i], !val[i]};
    update(p[i]);
  }
  return memo[0].fr;
}

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