Submission #1264872

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264872		silentloop	Digital Circuit (IOI22_circuit)	C++20	7 / 100	3025 ms	12884 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], hijos[MAXN];

ll n, m, tot = 0;

pair<ll, ll> dfs(ll nod) // fr: posibilidades activo, se: posibilidades apagado
{
  if (nod >= n)
    return {val[nod], !val[nod]};
  vector<ll> a(hijos[nod], 0);
  a[0] = 1;
  pair<ll, ll> cant = {-1, 0};
  ll i=0;
  for (auto k : grafo[nod])
  {
    i++;
    pair<ll, ll> ret = dfs(k);
    pair<ll, ll> un = {0,0};
    if (cant.fr == -1)
    {
      cant = ret;
      continue;
    }
    un.fr=(i*(cant.fr*ret.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)
    un.fr=(un.fr+(cant.fr*ret.se)%MOD)%MOD; // solo el de la izquierda activo
    un.fr=(un.fr+(ret.fr*cant.se)%MOD)%MOD; // solo el de la derecha activo
    un.se=(i*(cant.se*ret.se)%MOD)%MOD; // los 2 apagados
    un.se=(un.se+(cant.fr*ret.se)%MOD)%MOD; // solo 1 activo con al menos 2 activos
    un.se=(un.se+(cant.se*ret.fr)%MOD)%MOD; // solo 1 activo con al menos 2 activos
    cant=un;
  }
  return cant;
}

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

ll in(ll nod)
{
  hijos[nod] = 1;
  for (auto k : grafo[nod])
  {
    hijos[nod] += in(k);
  }
  return hijos[nod];
}

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

int count_ways(int L, int R)
{
  ll i;
  for (i = L; i <= R; i++)
    val[i] = !val[i];
  calc();
  return tot;
}

• Subtask 1: 0 / 2
• Subtask 2: 7 / 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