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;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
ll ttt;
const ll INF=1e18;
const ll MOD=1e9+2022;
const ll N=200007;
ll n,m,k;
vector<ll>g[N];
vector<ll>p;
vector<ll>a;
ll tot[N];
ll dp[N];
void calc_tot(ll v){
if(!g[v].size()){tot[v]=1;return;}
tot[v]=g[v].size();
for(ll to:g[v]){
calc_tot(to);
tot[v]*=tot[to];
tot[v]%=MOD;
}
}
void calc_dp(ll v){
if(!g[v].size()){
dp[v]=a[v];
return;
}
for(ll to:g[v])calc_dp(to);
vector<ll>d;
ll cur=1;
for(ll to:g[v]){
d.push_back(cur);
cur*=tot[to];
cur%=MOD;
}
cur=1;
ll sum=0;
// cout<<"DDDDD\n";
for(ll i=g[v].size()-1;i>=0;i--){
// cout<<g[v][i]<<": "<<d[i]<<" ";
d[i]*=cur;
d[i]%=MOD;
// cout<<d[i]<<" ";
d[i]*=dp[g[v][i]];
d[i]%=MOD;
// cout<<d[i]<<endl;
sum+=d[i];
sum%=MOD;
cur*=tot[g[v][i]];
cur%=MOD;
}
dp[v]=sum;
}
void just_calc_dp(ll v){
if(!g[v].size()){
dp[v]=a[v];
return;
}
// for(ll to:g[v])calc_dp(to);
vector<ll>d;
ll cur=1;
for(ll to:g[v]){
d.push_back(cur);
cur*=tot[to];
cur%=MOD;
}
cur=1;
ll sum=0;
// cout<<"DDDDD\n";
for(ll i=g[v].size()-1;i>=0;i--){
// cout<<g[v][i]<<": "<<d[i]<<" ";
d[i]*=cur;
d[i]%=MOD;
// cout<<d[i]<<" ";
d[i]*=dp[g[v][i]];
d[i]%=MOD;
// cout<<d[i]<<endl;
sum+=d[i];
sum%=MOD;
cur*=tot[g[v][i]];
cur%=MOD;
}
dp[v]=sum;
}
void go_up(int v){
just_calc_dp(v);
while(v!=0){
v=p[v];
just_calc_dp(v);
}
}
void init(int NN, int MM, vector<int> P, vector<int> A) {
n=NN;
m=MM;
for(ll v=1;v<n+m;v++){
g[P[v]].push_back(v);
// g[v].push_back(P[v]);
}
for(int x:P)p.push_back(x);
a.resize(n+m,0);
for(ll i=0;i<m;i++){
a[i+n]=A[i];
}
calc_tot(0);
calc_dp(0);
// for(ll v=0;v<n+m;v++){
// cout<<v<<": "<<tot[v]<<endl;
// }
}
int count_ways(int L, int R) {
for(ll i=L;i<=R;i++){
a[i]=!a[i];
go_up(i);
}
// calc_dp(0);
// for(ll v=0;v<n+m;v++){
// cout<<v<<": "<<dp[v]<<", "<<a[v]<<endl;
// }
return dp[0];
}
# | 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... |