Submission #1236293

#TimeUsernameProblemLanguageResultExecution timeMemory
1236293AMel0nDigital Circuit (IOI22_circuit)C++20
18 / 100
3048 ms7340 KiB
// I'm a bit stupid (2 remade) #include <bits/stdc++.h> using namespace std; typedef long long ll; #define FOR(i,N) for(ll i = 0; i < N; i++) #define all(x) (x).begin(), (x).end() #define F first #define S second #include "circuit.h" const ll MOD = 1000002022; int N, M; vector<vector<int>> C; vector<int> A; vector<vector<ll>> dp; void dfs(int n) { if (n >= N) {dp[n][A[n-N]] = 1; dp[n][!A[n-N]] = 0; return ;} for(int c: C[n]) { dfs(c); } int k = C[n].size(); vector<ll> knap(k+1); knap[0] = 1; for(int c: C[n]) { ll a0 = (c >= N) ? (1 - A[c-N]) : dp[c][0]; ll a1 = (c >= N) ? A[c-N] : dp[c][1]; vector<ll> neww(k+1); FOR(i, k+1) { if (knap[i]) { neww[i] = (neww[i] + knap[i] * a0) % MOD; neww[i+1] = (neww[i+1] + knap[i] * a1) % MOD; } } knap = neww; } ll tot1 = 0, tot0 = 0; FOR(i, k+1) { tot1 = (tot1 + knap[i] * i) % MOD; tot0 = (tot0 + knap[i] * (k-i)) % MOD; } dp[n][0] = tot0; dp[n][1] = tot1; } void init(int N, int M, std::vector<int> P, std::vector<int> A) { ::N = N; ::M = M; ::A = A; C.resize(N+M); dp.resize(N+M, vector<ll>(2)); for(int i = 1; i < N+M; i++) C[P[i]].push_back(i); } int count_ways(int L, int R) { for(int i = L-N; i <= R-N; i++) A[i] = !A[i]; 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...