Submission #627375

#TimeUsernameProblemLanguageResultExecution timeMemory
627375ElegiaDigital Circuit (IOI22_circuit)C++17
18 / 100
3043 ms3620 KiB
#include "circuit.h" #include <algorithm> #include <iostream> #include <vector> using ull = unsigned long long; const int MOD = 1000002022; int N, M; std::vector<int> P, A, prod; std::vector<std::vector<int>> ch; void init(int _N, int _M, std::vector<int> _P, std::vector<int> _A) { N = _N; M = _M; P = _P; prod.resize(N + M); std::fill(prod.begin() + N, prod.end(), 1); for (int i = 1; i != N + M; ++i) ++prod[P[i]]; for (int i = N - 1; i; --i) prod[P[i]] = prod[P[i]] * (ull)prod[i] % MOD; A.resize(N + M); std::copy(_A.begin(), _A.end(), A.begin() + N); ch.resize(N); for (int i = 1; i != N + M; ++i) ch[P[i]].push_back(i); } int count_ways(int L, int R) { for (int i = L; i <= R; ++i) A[i] = !A[i]; for (int i = N - 1; i >= 0; --i) { int f0 = 1, f1 = 0; for (int j : ch[i]) { f1 = (f0 * (ull)A[j] + f1 * (ull)prod[j]) % MOD; f0 = f0 * (ull)prod[j] % MOD; } A[i] = f1; } return A[0]; }
#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...