Submission #1211647

#TimeUsernameProblemLanguageResultExecution timeMemory
1211647serkanrashidDigital Circuit (IOI22_circuit)C++20
0 / 100
3066 ms5728 KiB
#include <bits/stdc++.h> #define endl "\n" using namespace std; const long long mod = 1e9 + 2022; const int MAXN = 1e5+5; int n,m; int p[MAXN],a[MAXN]; vector<int>g[MAXN]; void init(int N, int M, vector<int> P, vector<int> A) { n = N; m = M; for(int i = 0; i < n+m; i++) { p[i] = P[i]; g[p[i]].push_back(i); } for(int i = 0; i < m; i++) a[i] = A[i]; } long long dp[MAXN][2]; void dfs(int beg) { if(beg >= n) return; for(int nb : g[beg]) dfs(nb);///smetnati int sz = g[beg].size(); for(int mask = 0; mask < (1<<sz); mask++) { long long v = 1; int br1 = 0; for(int j = 0; j < sz; j++) { int ne = 0; if(mask & (1<<j)) ne = 1; br1 += ne; v *= dp[g[beg][j]][ne]; v %= mod; } dp[beg][1] += (v*(sz-br1+1))%mod; dp[beg][1] %= mod; dp[beg][0] += (v*br1)%mod; dp[beg][0] %= mod; } } void solve() { for(int i = 0; i < n+m; i++) dp[i][0] = dp[i][1] = 0; for(int i = 0; i < m; i++) dp[i+n][a[i]] = 1; dfs(0); } int count_ways(int L, int R) { for(int i = L; i <= R; i++) a[i] ^= 1; solve(); return (int)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...