Submission #1247456

#TimeUsernameProblemLanguageResultExecution timeMemory
1247456m5588ohammedDigital Circuit (IOI22_circuit)C++20
0 / 100
10 ms8788 KiB
#include "circuit.h" #include <bits/stdc++.h> using namespace std; #define mod 1000002022 #define ll long long ll n,m; ll to[5001],tf[5001],cs[200001]; vector <ll> v[200001]; vector <vector<ll>> dp[5001]; ll calc(ll i,ll j,ll k){ if(j==(int)v[i].size()){ if(k==0) return dp[i][j][k]=1; else return dp[i][j][k]=0; } if(dp[i][j][k]!=-1) return dp[i][j][k]; ll ans=0; if(k!=0) ans+=(calc(i,j+1,k-1)*to[v[i][j]])%mod; ans%=mod; ans+=(calc(i,j+1,k)*(tf[v[i][j]]-to[v[i][j]]+mod))%mod; ans%=mod; return dp[i][j][k]=ans; } void solve(ll i){ to[i]=tf[i]=0; for(int j=0;j<=v[i].size();j++){ for(int k=0;k<=v[i].size();k++) dp[i][j][k]=-1; } if(n<=i){ if(cs[i]==1) to[i]=1; else to[i]=0; tf[i]=1; //cout<<i<<" "<<to[i]<<" "<<tf[i]<<endl; return; } //cout<<"YUP"<<" "<<i<<" "<<v[i].size()<<endl; tf[i]=1; for(ll j:v[i]){ solve(j); tf[i]=(tf[i]*tf[j])%mod; } tf[i]*=(int)v[i].size(); tf[i]%=mod; for(ll k=1;k<=v[i].size();k++){ calc(i,0,k); to[i]=(to[i]+dp[i][0][k]*k)%mod; //cout<<"HERE "<<i<<" "<<k<<" "<<dp[i][0][k]<<endl; } //cout<<i<<" "<<to[i]<<" "<<tf[i]<<endl; return; } void init(int N, int M, std::vector<int> P, std::vector<int> A) { n=N;m=M; for(int i=0;i<m;i++) cs[i+n]=A[i]; for(int i=1;i<n+m;i++) v[P[i]].push_back(i); for(int i=0;i<n;i++){ ll siz=v[i].size(); dp[i].resize(siz+2,vector <ll> (siz+2)); } //cout<<"HERE "<<cs[3]<<" "<<cs[4]<<endl; //cout<<"END BUILD"<<endl; return; } int count_ways(int L, int R){ for(int i=L;i<=R;i++) { cs[i]^=1; } // for(int i=n;i<n+m;i++) cout<<cs[i]<<" "; // cout<<endl; solve(0); //cout<<"YES"<<endl; // cout<<"HERE "<<cs[6]<<" "<<cs[5]<<endl; //cout<<"END"<<endl; return to[0]; } // 3 4 3 // -1 0 1 2 1 1 0 // 1 0 1 0 // 3 4 // 4 5 // 3 6 // 1 7 3 // -1 0 0 0 0 0 0 0 // 1 1 1 1 1 1 1 // 1 1 // 2 2 // 4 7
#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...