Submission #1236265

#TimeUsernameProblemLanguageResultExecution timeMemory
1236265AMel0nDigital Circuit (IOI22_circuit)C++20
0 / 100
3047 ms7452 KiB
// I'm a bit stupid (1) #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<int>> 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); } dp[n][0] = dp[C[n][0]][0] * dp[C[n][1]][1] + dp[C[n][0]][1] * dp[C[n][1]][0] + 2 * dp[C[n][0]][0] * dp[C[n][1]][0]; dp[n][1] = dp[C[n][0]][0] * dp[C[n][1]][1] + dp[C[n][0]][1] * dp[C[n][1]][0] + 2 * dp[C[n][0]][1] * dp[C[n][1]][1]; } 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<int>(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...