#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;
for (auto k : grafo[nod])
{
pair<ll, ll> ret = dfs(k);
pair<ll, ll> un = {0,0};
if (cant.fr == -1)
{
cant = ret;
continue;
}
un.fr = (un.fr + (cant.fr * ret.fr) % MOD) % MOD;
un.fr = (un.fr + (cant.se * ret.fr) % MOD) % MOD;
un.fr = (un.fr+ret.fr)%MOD;
un.se=(un.se+ret.se)%MOD;
un.se = (un.se + (cant.se * ret.se) % MOD) % MOD;
un.se = (un.se + (cant.fr * ret.se) % MOD) % MOD;
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... |