Submission #1077365

#TimeUsernameProblemLanguageResultExecution timeMemory
1077365UmairAhmadMirzaDigital Circuit (IOI22_circuit)C++17
0 / 100
655 ms19924 KiB
#include "circuit.h" #include <bits/stdc++.h> using namespace std; #define ll long long int const N=3e5+5; ll const mod=1000002022; vector<int> child[N]; ll on[N],off[N],tot[N]; vector<ll> dp[N]; int n,m; vector<int> par,st; int dep[N]; void dfs(int node){ for(int i:child[node]){ dep[i]=dep[node]+1; dfs(i); } } bool vis[N]; void compute(int node){ int c=child[node].size(); tot[node]=c; for(int i:child[node]) tot[node]*=tot[i]; for (int i = 0; i <=c; ++i) { dp[i].clear(); dp[i].resize(c+5,0); } dp[1][1]=on[child[node][0]]; dp[1][0]=off[child[node][0]]; for(int i=2;i<=c;i++){ for(int j=0;j<=i;j++) { dp[i][j]=(dp[i-1][j]*off[child[node][i-1]])%mod; if(j==0) continue; dp[i][j]+=(dp[i-1][j-1]*on[child[node][i-1]]%mod); dp[i][j]%=mod; } // cout<<endl; } on[node]=0; for(int i=1;i<=c;i++) on[node]=(on[node]+((dp[c][i]*i)%mod))%mod; off[node]=((tot[node]-on[node])+mod)%mod; } void init(int nn, int mm, vector<int> P, vector<int> A){ // cerr<<"GOT"<<endl; n=nn; m=mm; par=P; st=A; for(int i=1;i<n+m;i++) child[par[i]].push_back(i); dfs(0); priority_queue<pair<int,int>> q; for(int i=n;i<n+m;i++){ tot[i]=1; if(st[i-n]==1){ on[i]=1; off[i]=0; } else{ on[i]=0; off[i]=1; } // cout<<on[i]<<' '<<off[i]<<' '<<tot[i]<<endl; q.push({dep[par[i]],par[i]}); } while(q.size()){ int node=(q.top()).second; q.pop(); if(node==-1) continue; compute(node); q.push({dep[par[node]],par[node]}); } // for (int i = 0; i < n; ++i) // cout<<on[i]<<' '<<off[i]<<' '<<tot[i]<<endl; } int count_ways(int L, int R){ // cout<<"L R := "<<L<<' '<<R<<endl; // for (int i = 0; i < n+m; ++i) // vis[i]=0; priority_queue<pair<int,int>> q; for(int i=L;i<=R;i++){ st[i-n]^=1; if(st[i-n]==1){ on[i]=1; off[i]=0; } else{ on[i]=0; off[i]=0; } q.push({dep[par[i]],par[i]}); } while(q.size()){ int node=(q.top()).second; q.pop(); if(node==-1) continue; // vis[node]=1; // cout<<node<<endl; compute(node); q.push({dep[par[node]],par[node]}); } // for (int i = 0; i < n+m; ++i) // cout<<on[i]<<' '<<off[i]<<' '<<tot[i]<<endl; return on[0]; }
#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...