# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1028321 | 42kangaroo | Digital Circuit (IOI22_circuit) | C++17 | 3048 ms | 3344 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "circuit.h"
#include <vector>
using namespace std;
vector<int> a;
using g_t = vector<vector<int>>;
g_t g;
using ll = long long;
constexpr ll mod = 1000002022;
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
g = g_t(N);
for (int i = 1; i < N + M; ++i) {
g[P[i]].push_back(i);
}
a = A;
}
int count_ways(int L, int R) {
L -= g.size();
R -= g.size();
for (int i = L; i <= R; ++i) {
a[i] = 1 - a[i];
}
vector<ll> nuP(g.size()), nuT(g.size());
for (int i = g.size() - 1; i >= 0; --i) {
ll su = 1;
ll suMult = 0;
nuT[i] = g[i].size();
for (auto e: g[i]) {
if (e >= g.size()) {
if (a[e - g.size()] == 1) {
suMult = suMult + su;
suMult %= mod;
}
} else {
nuT[i] = (nuT[i] * nuT[e]) % mod;
suMult = ((suMult * nuT[e]) % mod + (su * nuP[e]) % mod + mod) % mod;
su = (nuT[e] * su) % mod;
}
}
nuP[i] = suMult;
}
return nuP.front();
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |