#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=0;
for (auto k : grafo[nod])
{
i++;
pair<ll, ll> ret = dfs(k);
pair<ll, ll> un = {0,0};
if (cant.fr == -1)
{
cant = ret;
continue;
}
un.fr=(i*(cant.fr*ret.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)
un.fr=(un.fr+(cant.fr*ret.se)%MOD)%MOD; // solo el de la izquierda activo
un.fr=(un.fr+(ret.fr*cant.se)%MOD)%MOD; // solo el de la derecha activo
un.se=(i*(cant.se*ret.se)%MOD)%MOD; // los 2 apagados
un.se=(un.se+(cant.fr*ret.se)%MOD)%MOD; // solo 1 activo con al menos 2 activos
un.se=(un.se+(cant.se*ret.fr)%MOD)%MOD; // solo 1 activo con al menos 2 activos
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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |