#include<bits/stdc++.h>
#include "circuit.h"
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
const int mod=1000002022;
const int maxn=2e5;
vector<int>adj[maxn];
vector<int>a;
int n,m;
void init(int N,int M,vector<int>p,vector<int>A){
n=N;
m=M;
a=A;
for(int i=1;i<n+m;i++){
adj[p[i]].pb(i);
}
}
int count_ways(int l,int r){
if(n==1){
l-=n;
r-=n;
int cnt=0;
for(int i=0;i<m;i++){
if(l<=i&&i<=r){
a[i]=1-a[i];
}
cnt+=a[i];
}
return cnt;
}
l-=n;
r-=n;
for(int i=l;i<=r;i++){
a[i]=1-a[i];
}
int ans=0;
int cnt[n+m+5][2];//number of ways end with 0/1
for(int j=n;j<n+m;j++){
cnt[j][a[j-n]]=1;
cnt[j][1-a[j-n]]=0;
}
for(int i=n-1;i>=0;i--){
int sz=adj[i].size();
int dp[sz+1];
fill(dp,dp+sz+1,0);
dp[0]=1;
int cur=0;
for(int x:adj[i]){
cur++;
for(int j=cur-1;j>=0;j--){
dp[j+1]+=1ll*dp[j]*cnt[x][1];
dp[j+1]%=mod;
dp[j]+=1ll*dp[j]*cnt[x][0];
dp[j]%=mod;
}
}
int c1=0,c0=0;
for(int j=0;j<=cur;j++){
c1+=dp[j];
c1%=mod;
}
for(int j=cur;j>=1;j--){
cnt[i][1]+=c1;
cnt[i][1]%=mod;
cnt[i][0]+=c0;
cnt[i][0]%=mod;
c0=(c0+dp[j])%mod;
c1=(c1-dp[j]+mod)%mod;
}
}
return cnt[0][1];
}
Compilation message
circuit.cpp: In function 'int count_ways(int, int)':
circuit.cpp:47:9: warning: unused variable 'ans' [-Wunused-variable]
47 | int ans=0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4952 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4952 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
4964 KB |
1st lines differ - on the 1st token, expected: '52130940', found: '377234552' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4952 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
4964 KB |
1st lines differ - on the 1st token, expected: '52130940', found: '377234552' |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3022 ms |
7060 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3022 ms |
7060 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
4964 KB |
1st lines differ - on the 1st token, expected: '52130940', found: '377234552' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4952 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
4964 KB |
1st lines differ - on the 1st token, expected: '52130940', found: '377234552' |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4952 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
4964 KB |
1st lines differ - on the 1st token, expected: '52130940', found: '377234552' |
| 11 |
Halted |
0 ms |
0 KB |
- |
