Submission #1264898

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264898		silentloop	Digital Circuit (IOI22_circuit)	C++20	2 / 100	3008 ms	7552 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]};
  pair<ll, ll> cant = {0, 0};
  ll i=0, tot=1;
  for (auto k : grafo[nod])
  {
    i++;
    pair<ll,ll>a=dfs(k);
    cant.fr=(cant.fr+(a.fr*tot)%MOD)%MOD;
    tot=(tot*(a.fr+a.se)%MOD)%MOD;
  }
  cant.se=tot*(hijos[nod]-1)%MOD;
  cant.se=(cant.se-cant.fr)%MOD;
  if(cant.se<0)
    cant.se=cant.se+MOD;
  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: 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