Submission #1264914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264914		silentloop	Digital Circuit (IOI22_circuit)	C++20	9 / 100	3036 ms	7044 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];

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;
  vector<pair<ll,ll>>s;
  vector<ll>pref,suf;
  for (auto k : grafo[nod])
  {
    i++;
    pair<ll,ll>a=dfs(k);
    s.pb(a);
    tot=(tot*(a.fr+a.se)%MOD)%MOD;
  }
  pref.resize(sz(s));
  pref[0]=1;
  suf.resize(sz(s));
  suf[sz(suf)-1]=1;
  for(i=1; i<sz(s); i++)
    pref[i]=(pref[i-1]*(s[i-1].fr+s[i-1].se)%MOD)%MOD;
  for(i=sz(s)-2; i>=0; i--)
    suf[i]=(suf[i+1]*(s[i+1].fr+s[i+1].se)%MOD)%MOD;

  for(i=0; i<sz(s); i++)
    cant.fr=(cant.fr+(s[i].fr*(pref[i]*suf[i])%MOD)%MOD)%MOD;

  cant.se=(tot*sz(grafo[nod]))%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;
}



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];
  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: 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