Submission #1264731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264731		silentloop	Digital Circuit (IOI22_circuit)	C++20	0 / 100	3067 ms	8296 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;
  for (auto k : grafo[nod])
  {
    pair<ll, ll> ret = dfs(k);
    pair<ll, ll> un = {0,0};
    if (cant.fr == -1)
    {
      cant = ret;
      continue;
    }
    un.fr = (un.fr + (cant.fr * ret.fr) % MOD) % MOD;
    un.fr = (un.fr + (cant.se * ret.fr) % MOD) % MOD;
    un.fr = (un.fr+ret.fr)%MOD;

    un.se=(un.se+ret.se)%MOD;
    un.se = (un.se + (cant.se * ret.se) % MOD) % MOD;
    un.se = (un.se + (cant.fr * ret.se) % MOD) % MOD;
    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: 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