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 pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 3e5;
const ll MOD = 1e9+2022;
int N, M;
vector<int> adj[MAXN+10];
ll phi[MAXN+10];
vector<ll> PV[MAXN+10], SV[MAXN+10];
int S[MAXN+10];
ll A[MAXN+10];
void dfs(int now)
{
if(adj[now].empty())
{
phi[now]=1;
return;
}
phi[now]=adj[now].size();
for(auto nxt : adj[now])
{
dfs(nxt);
PV[now].push_back(phi[nxt]);
SV[now].push_back(phi[nxt]);
phi[now]=phi[now]*phi[nxt]%MOD;
}
for(int i=1; i<PV[now].size(); i++) PV[now][i]=PV[now][i-1]*PV[now][i]%MOD;
for(int i=SV[now].size()-2; i>=0; i--) SV[now][i]=SV[now][i+1]*SV[now][i]%MOD;
}
void dfs2(int now, ll val)
{
if(adj[now].empty())
{
A[now]=val;
return;
}
for(int i=0; i<adj[now].size(); i++)
{
int nxt=adj[now][i];
ll t=1;
if(i-1>=0) t=t*PV[now][i-1]%MOD;
if(i+1<SV[now].size()) t=t*SV[now][i+1]%MOD;
dfs2(nxt, val*t%MOD);
}
}
ll ans=0;
void init(int _N, int _M, vector<int> _P, vector<int> _Q)
{
N=_N; M=_M;
for(int i=1; i<N+M; i++) adj[_P[i]].push_back(i);
for(int i=N; i<N+M; i++) S[i]=_Q[i-N];
dfs(0);
dfs2(0, 1);
for(int i=N; i<N+M; i++) if(S[i]) ans=(ans+A[i])%MOD;
//for(int i=N; i<N+M; i++) printf("%lld ", A[i]); printf("\n");
}
int count_ways(int L, int R)
{
for(int i=L; i<=R; i++)
{
if(S[i]) ans=(ans-A[i])%MOD;
else ans=(ans+A[i])%MOD;
if(ans<0) ans+=MOD;
S[i]=!S[i];
}
return ans;
}
Compilation message (stderr)
circuit.cpp: In function 'void dfs(int)':
circuit.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for(int i=1; i<PV[now].size(); i++) PV[now][i]=PV[now][i-1]*PV[now][i]%MOD;
| ~^~~~~~~~~~~~~~~
circuit.cpp: In function 'void dfs2(int, ll)':
circuit.cpp:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int i=0; i<adj[now].size(); i++)
| ~^~~~~~~~~~~~~~~~
circuit.cpp:50:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | if(i+1<SV[now].size()) t=t*SV[now][i+1]%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... |