Submission #1264705

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

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}, 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
    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: 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