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;
const long long modulo = 1e9+2022;
namespace {
int N,M;
vector<vector<int>> adj;
vector<int> A,P;
vector<pair<long long,long long>> DPtree;
vector<int> updated;
int Q;
}
void init(int N,int M,vector<int> P,vector<int> A){
::N = N;
::M = M;
::A = A;
::P = P;
Q = 0;
updated = vector<int>(N+M);
DPtree = vector<pair<long long,long long>>(N);
adj = vector<vector<int>>(N);
for(int i=1;i<N+M;i++)adj[P[i]].emplace_back(i);
function<pair<long long,long long>(int)> dfs = [&](int x)->pair<long long,long long>{
if(x>=N) {
return {A[x-N],1};
}
long long tot_ways = adj[x].size();
vector<long long> DP(adj[x].size()+1);
DP[0]=1;
for(int&i:adj[x]) {
auto temp = dfs(i);
tot_ways*=temp.second;
tot_ways%=modulo;
long long bad_ways = (temp.second-temp.first+modulo)%modulo;
for(int j=adj[x].size();j>=0;j--) {
DP[j]*=bad_ways;
DP[j]%=modulo;
if(j)DP[j]+=temp.first*DP[j-1];
DP[j]%=modulo;
}
}
long long ans = 0;
for(long long i=1;i<=adj[x].size();i++) {
ans+=DP[i]*i;
ans%=modulo;
}
DPtree[x]={ans,tot_ways};
return {ans,tot_ways};
};
dfs(0);
}
int count_ways(int L,int R){
A[L-N]^=1;
Q++;
int curr = L;
while(curr>=0) {
updated[curr]=Q;
curr=P[curr];
}
function<pair<long long,long long>(int)> dfs = [&](int x)->pair<long long,long long>{
if(x>=N) {
return {A[x-N],1};
}
if(updated[x]<Q)return DPtree[x];
long long tot_ways = adj[x].size();
vector<long long> DP(adj[x].size()+1);
DP[0]=1;
for(int&i:adj[x]) {
auto temp = dfs(i);
tot_ways*=temp.second;
tot_ways%=modulo;
long long bad_ways = (temp.second-temp.first+modulo)%modulo;
for(int j=adj[x].size();j>=0;j--) {
DP[j]*=bad_ways;
DP[j]%=modulo;
if(j)DP[j]+=temp.first*DP[j-1];
DP[j]%=modulo;
}
}
long long ans = 0;
for(long long i=1;i<=adj[x].size();i++) {
ans+=DP[i]*i;
ans%=modulo;
}
DPtree[x]={ans,tot_ways};
return {ans,tot_ways};
};
return dfs(0).first;
}
Compilation message (stderr)
circuit.cpp: In lambda function:
circuit.cpp:46:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(long long i=1;i<=adj[x].size();i++) {
| ~^~~~~~~~~~~~~~~
circuit.cpp: In lambda function:
circuit.cpp:85:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(long long i=1;i<=adj[x].size();i++) {
| ~^~~~~~~~~~~~~~~
# | 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... |