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;
#define ll long long
ll const N=3e5+5;
ll const mod=1000002022;
vector<ll> child[N];
ll on[N],off[N],tot[N];
vector<ll> dp[N];
ll n,m;
vector<int> par,st;
ll dep[N];
void dfs(ll node){
for(ll i:child[node]){
dep[i]=dep[node]+1;
dfs(i);
}
}
ll vis[N];
void compute(ll node){
ll c=child[node].size();
tot[node]=c;
for(ll i:child[node])
tot[node]*=tot[i];
for (ll i = 0; i <=c+2; ++i)
{
dp[i].clear();
dp[i].resize(c+5,0);
}
dp[1][1]=on[child[node][0]];
dp[1][0]=off[child[node][0]];
for(ll i=2;i<=c;i++){
for(ll j=0;j<=i;j++)
{
dp[i][j]=(dp[i-1][j]*off[child[node][i-1]]%mod)%mod;
if(j==0)
continue;
dp[i][j]+=((dp[i-1][j-1]*on[child[node][i-1]])%mod);
dp[i][j]%=mod;
}
// cout<<endl;
}
on[node]=0;
for(ll i=1;i<=c;i++)
on[node]=(on[node]+((dp[c][i]*i)%mod))%mod;
off[node]=(((tot[node]-on[node])%mod)+mod)%mod;
}
void init(int nn, int mm, vector<int> P, vector<int> A){
// cerr<<"GOT"<<endl;
n=nn;
m=mm;
par=P;
st=A;
for(ll i=1;i<n+m;i++)
child[par[i]].push_back(i);
dfs(0);
priority_queue<pair<ll,ll>> q;
for(ll i=n;i<n+m;i++){
tot[i]=1;
if(st[i-n]==1){
on[i]=1;
off[i]=0;
}
else{
on[i]=0;
off[i]=1;
}
// cout<<on[i]<<' '<<off[i]<<' '<<tot[i]<<endl;
q.push({dep[par[i]],par[i]});
}
while(q.size()){
ll node=(q.top()).second;
q.pop();
if(node==-1 || vis[node]>=2)
continue;
vis[node]++;
compute(node);
q.push({dep[par[node]],par[node]});
}
// for (ll i = 0; i < n; ++i)
// cout<<on[i]<<' '<<off[i]<<' '<<tot[i]<<endl;
}
int count_ways(int L, int R){
// cout<<"L R := "<<L<<' '<<R<<endl;
for (ll i = 0; i < n+m; ++i)
vis[i]=0;
priority_queue<pair<ll,ll>> q;
for(ll i=L;i<=R;i++){
st[i-n]^=1;
tot[i]=1;
if(st[i-n]==1){
on[i]=1;
off[i]=0;
}
else{
on[i]=0;
off[i]=1;
}
q.push({dep[par[i]],par[i]});
}
while(q.size()){
ll node=(q.top()).second;
q.pop();
if(node==-1 || vis[node]>=2)
continue;
vis[node]++;
// cout<<node<<endl;
compute(node);
q.push({dep[par[node]],par[node]});
}
// for (ll i = 0; i < n+m; ++i)
// cout<<on[i]<<' '<<off[i]<<' '<<tot[i]<<endl;
return on[0]%mod;
}
# | 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... |