Submission #915231

#TimeUsernameProblemLanguageResultExecution timeMemory
915231NamkhingDigital Circuit (IOI22_circuit)C++17
7 / 100
3009 ms6488 KiB
#include "circuit.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int Max = 1e5 + 1; const int Mod = 1e9 + 2022; ll n, m, dp[Max << 1][2]; vector<int> adj[Max]; void init(int N, int M, vector<int> P, vector<int> A) { n = N, m = M; for (int i = 1; i < N + M; i++) { adj[P[i]].push_back(i); } for (int i = 0; i < M; i++) { dp[N + i][A[i]] = 1; } } int count_ways(int L, int R) { for (int i = L; i <= R; i++) { swap(dp[i][0], dp[i][1]); } for (int i = n - 1; i >= 0; i--) { int l = adj[i][0]; int r = adj[i][1]; dp[i][0] = (dp[l][1] * dp[r][0] + dp[l][0] * dp[r][1] + 2 * dp[l][0] * dp[r][0]) % Mod; dp[i][1] = (dp[l][1] * dp[r][0] + dp[l][0] * dp[r][1] + 2 * dp[l][1] * dp[r][1]) % Mod; } 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...