Submission #1264706

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