Submission #1077381

#TimeUsernameProblemLanguageResultExecution timeMemory
1077381UmairAhmadMirzaDigital Circuit (IOI22_circuit)C++17
2 / 100
750 ms22868 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(); for (int i = 0; i <=c+2; ++i) { dp[i].clear(); for (int j = 0; j < c+5; ++j) dp[i].push_back(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)%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; } tot[node]=(dp[c][0]*c)%mod; on[node]=0; for(ll i=1;i<=c;i++) on[node]=(on[node]+((dp[c][i]*i)%mod))%mod; off[node]=(((tot[node]-on[node])%mod)+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; } for(int i=0;i<n+m;i++) q.push({dep[par[i]],par[i]}); while(q.size()){ int node=(q.top()).second; q.pop(); if(node==-1 || vis[node]) continue; vis[node]=1; 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; tot[i]=1; if(st[i-n]==1){ on[i]=1; off[i]=0; } else{ on[i]=0; off[i]=1; } q.push({dep[par[i]],par[i]}); } while(q.size()){ int node=(q.top()).second; q.pop(); if(node==-1 || vis[node]) 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]%mod; }
#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...