Submission #1077442

#TimeUsernameProblemLanguageResultExecution timeMemory
1077442Faisal_SaqibDigital Circuit (IOI22_circuit)C++17
18 / 100
3010 ms15432 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const ll NP=1e5+100,mod=1e9+2022; ll n,m,p[NP],a[NP]; vector<ll> ma[NP]; ll dp[NP][2]; void compute(int x,bool recur=1) { dp[x][0]=dp[x][1]=0; if(n<=x){ dp[x][a[x-n]]=1; return; } int sz=ma[x].size(); vector<int> tmp(sz+1); tmp[0]=1; for(auto y:ma[x]) { if(recur) compute(y); for(int j=sz;j>=0;j--) { if(j==0) { tmp[j]=(tmp[j]*dp[y][0])%mod; } else { tmp[j]=(tmp[j]*dp[y][0])%mod; tmp[j]=(tmp[j] + ((tmp[j-1]*dp[y][1])%mod))%mod; } } } int sm=0; for(int j=sz;j>=1;j--) { sm = ( sm + tmp[j] ) % mod; dp[x][1] = ( dp[x][1] + sm ) % mod; } sm=tmp[0]; for(int j=1;j<=sz;j++) { dp[x][0] = ( dp[x][0] + sm ) % mod; sm = ( sm + tmp[j] ) % mod; } } bool subtask=1; void init(int N, int M, std::vector<int> P, std::vector<int> A) { n=N,m=M; for(ll i=0;i<n+m;i++) { p[i]=P[i]; if(p[i]!=-1)ma[p[i]].push_back(i),subtask&=((p[i]==((i-1)/2))); } for(ll j=0;j<m;j++)a[j]=A[j]; compute(0); } int count_ways(int L, int R) { for(ll i=L-n;i<=R-n;i++)a[i]=(a[i]?0:1); if(L==R) { int x=L; while(x>=0) { compute(x,0); x=p[x]; } } else { compute(0); } return (int)dp[0][1]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...