Submission #1077813

#TimeUsernameProblemLanguageResultExecution timeMemory
1077813pccDigital Circuit (IOI22_circuit)C++17
2 / 100
3100 ms8024 KiB
#include "circuit.h" #include <vector> #include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define fs first #define sc second const int mxn = 2e5+10; const int mod = 100002022; vector<int> tree[mxn]; int par[mxn]; int N,M; ll dp[mxn][2]; ll mad(ll a,ll b){ a += b; return a>=mod?a-mod:a; } ll mub(ll a,ll b){ return mad(a,mod-b); } pll calc(vector<int>& a,vector<int>& b){ vector<vector<ll>> dp(2,vector<ll>(a.size()+1,0)); int r = 0; int s = a.size(); dp[r][0] = a[0]; dp[r][1] = b[0]; for(int i = 1;i<s;i++){ r ^= 1; fill(dp[r].begin(),dp[r].end(),0); for(int j = 0;j<=i+1;j++){ dp[r][j] = mad(dp[r][j],dp[r^1][j]*a[i]%mod); if(j)dp[r][j] = mad(dp[r][j],dp[r^1][j-1]*b[i]%mod); } } for(int i = 1;i<=s;i++){ dp[r][i] = mad(dp[r][i],dp[r][i-1]); } pll re = pll(0,0); for(int c = 1;c<=s;c++){ re.fs = mad(re.fs,dp[r][c-1]); re.sc = mad(re.sc,mub(dp[r][s],dp[r][c-1])); } /* cerr<<"CALC: "<<endl; for(auto &i:a)cerr<<i<<' ';cerr<<endl; for(auto &i:b)cerr<<i<<' ';cerr<<endl; for(auto &i:dp[r])cerr<<i<<' ';cerr<<endl; */ return re; } void dfs(int now){ if(tree[now].empty())return; vector<int> v1,v2; for(auto nxt:tree[now]){ dfs(nxt); v1.push_back(dp[nxt][0]); v2.push_back(dp[nxt][1]); } auto [a,b] = calc(v1,v2); dp[now][0] = a,dp[now][1] = b; //cerr<<now<<":"<<dp[now][0]<<' '<<dp[now][1]<<endl; return; } void init(int N1, int M1, std::vector<int> P, std::vector<int> A) { N = N1,M = M1; for(int i = 1;i<N+M;i++){ par[i] = P[i]; tree[par[i]].push_back(i); } for(int i = 0;i<M;i++){ dp[i+N][A[i]] = 1; } dfs(0); //for(int i = 0;i<N+M;i++)cerr<<dp[i][0]<<','<<dp[i][1]<<' ';cerr<<endl; } int count_ways(int L, int R) { for(int i = L;i<=R;i++){ dp[i][0] ^= 1; dp[i][1] ^= 1; } dfs(0); return 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...