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;
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;
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);
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};
}
for (int i = N - 1; i >= 0; i--)
calc(i);
}
int count_ways(int L, int R) {
set<int, greater<int>>Q;
for (int i = L; i <= R; i++)
{
swap(a[i].first, a[i].second);
Q.insert(P[i]);
}
while (!Q.empty())
{
int i = *(Q.begin());
Q.erase(Q.begin());
if (i != 0)
Q.insert(P[i]);
calc(i);
}
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... |