Submission #1247444

#TimeUsernameProblemLanguageResultExecution timeMemory
1247444ereringDigital Circuit (IOI22_circuit)C++20
2 / 100
13 ms17672 KiB
#include <bits/stdc++.h> #include "circuit.h" using namespace std; #define pb push_back #define ll long long const ll MAXN=1000+5,MOD=1000002022; ll n,m,cnt[MAXN],am[MAXN],suff[MAXN][MAXN]; vector<int> ch[MAXN]; ll dp[MAXN],prod[MAXN],num[MAXN][MAXN]; bool pos[MAXN]; //dp[i] ammount of ways to make i black. prod[i] how many ways to assign parameters in i subtree //num[i] how many ways such i of its threshold children are black void dfs(int node){ prod[node]=1; int seen=0; for(auto i:ch[node]){ if(i<n){ dfs(i); prod[node]*=prod[i]*am[i]%MOD; if(!pos[i])continue; seen++; for(int j=seen;j>0;j--){ num[node][j]+=num[node][j-1]+dp[i]; num[node][j]%=MOD; } } } // if(node==1)cout<<num[node][1]<<endl; for(int i=seen;i>0;i--)suff[node][i]=num[node][i]+suff[node][i+1]; //assign parammeter i to node for(int i=1;i<=am[node];i++){ if(cnt[node]>=i){ pos[node]=1; dp[node]+=prod[node]; dp[node]%=MOD; continue; } // cout<<"nah "<<i<<' '<<am[node]<<' '<<node<<' '<<cnt[node]<<endl; int req=i-cnt[node]; if(req>seen)continue; pos[node]=1; // cout<<"bro "<<i<<' '<<req<<' '<<suff[node][req]<<' '<<node<<endl; dp[node]+=suff[node][req]; dp[node]%=MOD; } // cout<<node<<' '<<dp[node]<<' '<<prod[node]<<endl; } vector<int> a,p; void init(int N, int M, std::vector<int> P, std::vector<int> A) { for(int i=0;i<MAXN;i++){ cnt[i]=0; am[i]=0; ch[i].clear(); dp[i]=0; pos[i]=0; for(int j=0;j<MAXN;j++){ suff[i][j]=0; num[i][j]=0; } } p=P; a=A; n=N; m=M; for(int i=1;i<P.size();i++){ ch[P[i]].pb(i); if(i>=n && A[i-N])cnt[P[i]]++; am[P[i]]++; } /* for(int i=0;i<n;i++)cout<<cnt[i]<<' '; cout<<endl; for(auto i:A)cout<<i<<' '; cout<<endl;*/ } int count_ways(int L, int R) { for(int i=L-n;i<=R-n;i++)a[i]^=1; // cout<<endl; init(n,m,p,a); // cout<<"goo"<<endl; dfs(0); return dp[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...