This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1000002022;
vector<pair<ll, ll>>a;
vector<int>P;
vector<int>A;
vector<vector<int>>c;
int N, M;
vector<bool> F(200009, false);
vector<int> L, R;
void calc(int i)
{
int d = c[i].size();
vector<ll> k(d + 2, 0ll);
k[0] = 1;
for (int j : c[i])
{
int v0 = a[j].first;
int v1 = a[j].second;
if (F[j])
swap(v0, v1);
for (int t = d; t >= 0; t--)
{
k[t + 1] += v1 * k[t];
k[t + 1] %= mod;
k[t] = v0 * k[t];
k[t] %= mod;
}
}
a[i] = {0ll, 0ll};
for (int t = 0; t <= d; t++)
{
a[i].second += k[t] * t;
a[i].second %= mod;
a[i].first += k[t] * (d - t);
a[i].first %= mod;
}
}
void init(int N_, int M_, vector<int> P_, vector<int> A_) {
P = P_;
A = A_;
N = N_;
M = M_;
a = vector<pair<ll, ll>>(N + M);
c = vector<vector<int>>(N + M);
L = vector<int>(N + M);
R = vector<int>(N + M);
for (int i = 1; i < N + M; i++)
c[P[i]].push_back(i);
for (int i = N + M - 1; i >= N; i--)
{
if (A[i - N] == 1)
a[i] = {0, 1};
else
a[i] = {1, 0};
L[i] = R[i] = i;
}
for (int i = N - 1; i >= 0; i--)
{
calc(i);
L[i] = N + M + 5;
R[i] = -1;
for (int j : c[i])
{
L[i] = min(L[i], L[j]);
R[i] = max(R[i], R[j]);
}
}
}
int count_ways(int X, int Y) {
function<void(int)>f = [&](int i)->void
{
if (R[i] < X || Y < L[i])
return;
if (X <= L[i] && R[i] <= Y)
{
F[i] = F[i] ^ true;
}
else
{
for (int j : c[i])
{
F[j] = F[j] ^ F[i];
f(j);
}
calc(i);
F[i] = false;
}
};
f(0);
if (F[0])
return a[0].first;
return (int)a[0].second;
}
# | 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... |