#include "circuit.h"
#include <vector>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<ll,ll> ii;
#define ff first
#define ss second
const int maxn = 2e5 + 10;
const ll mod = 1000002022LL;
int n,m;
int a[maxn];
vector <int> adj[maxn];
ll s[maxn],dp[maxn],sdp[maxn];
void dfs(int x)
{
s[x] = 1LL;
for (int i:adj[x])
{
dfs(i);
s[x]=s[x]*s[i]%mod;
}
s[x] = s[x]*(ll)adj[x].size()%mod;
}
void dfs2(int x, ll val)
{
if (x>=n)
{
dp[x-n+1] = val;
return;
}
vector <ll> pre,suf;
for (int i:adj[x])
{
pre.push_back(s[i]);
suf.push_back(s[i]);
}
for (int i=1; i<pre.size(); i++) pre[i]=pre[i]*pre[i-1]%mod;
for (int i=suf.size()-2; i>=0; i--) suf[i]=suf[i]*suf[i+1]%mod;
int cnt=0;
for (int i:adj[x])
{
ll val2 = val;
if (cnt>0) val2=val2*pre[cnt-1]%mod;
if (cnt<suf.size()-1) val2=val2*suf[cnt+1]%mod;
dfs2(i,val2);
}
}
ll f[4*maxn]; bool rev[4*maxn];
void pushrev(int x, int lx, int rx)
{
f[x] = (sdp[rx]-sdp[lx-1]+mod-f[x]+mod)%mod;
rev[x]^=1;
}
void down(int x, int lx, int rx)
{
if (lx==rx) return;
int mid=(lx+rx)/2;
if (rev[x])
{
pushrev(2*x,lx,mid);
pushrev(2*x+1,mid+1,rx);
rev[x]=0;
}
}
void add(int x, int lx, int rx, int l, int r)
{
if (lx>r||rx<l) return;
if (lx>=l&&rx<=r)
{
pushrev(x,lx,rx);
return;
}
int mid=(lx+rx)/2;
down(x,lx,rx);
add(2*x,lx,mid,l,r);
add(2*x+1,mid+1,rx,l,r);
f[x]=(f[2*x]+f[2*x+1])%mod;
}
void build(int x, int lx, int rx)
{
rev[x]=0;
if (lx==rx)
{
f[x]=0LL;
if (a[x]) f[x] = dp[x];
return;
}
int mid=(lx+rx)/2;
build(2*x,lx,mid); build(2*x+1,mid+1,rx);
f[x]=(f[2*x]+f[2*x+1])%mod;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n=N; m=M;
for (int i=0; i<n+m; i++) adj[i].clear();
for (int i=1; i<n+m; i++)
{
int u=i; int v=P[i];
adj[v].push_back(u);
}
for (int i=n; i<n+m; i++) a[i-n+1]=A[i-n];
dfs(1); dfs2(1,1LL);
sdp[0]=0LL;
for (int i=1; i<=m; i++) sdp[i]=(dp[i]+sdp[i-1])%mod;
build(1,1,m);
}
int count_ways(int L, int R) {
L++; R++;
add(1,1,m,L,R);
int ans = (f[1])%mod;
return ans;
}
Compilation message
circuit.cpp: In function 'void dfs2(int, long long int)':
circuit.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for (int i=1; i<pre.size(); i++) pre[i]=pre[i]*pre[i-1]%mod;
| ~^~~~~~~~~~~
circuit.cpp:46:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | if (cnt<suf.size()-1) val2=val2*suf[cnt+1]%mod;
| ~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4944 KB |
1st lines differ - on the 1st token, expected: '1', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4944 KB |
1st lines differ - on the 1st token, expected: '1', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4944 KB |
1st lines differ - on the 1st token, expected: '1', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
689 ms |
8180 KB |
1st lines differ - on the 1st token, expected: '431985922', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
689 ms |
8180 KB |
1st lines differ - on the 1st token, expected: '431985922', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4944 KB |
1st lines differ - on the 1st token, expected: '1', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4944 KB |
1st lines differ - on the 1st token, expected: '1', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4944 KB |
1st lines differ - on the 1st token, expected: '1', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
