#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD = 1'000'002'022;
template<class T>
ostream& operator<< (ostream &os, const vector<T> &arr) {
os << "[";
for (const T &v : arr) os << v << ", ";
return os << "]";
}
vector<ll> product_except(vector<ll> nums) {
int n = nums.size();
vector<ll> pref = nums, suff = nums;
for (int i = 1; i < n; ++i) pref[i] = (pref[i-1] * nums[i]) % MOD;
for (int i = n - 2; i >= 0; --i) suff[i] = suff[i+1] * nums[i] % MOD;
vector<ll> ans(n);
for (int i = 0; i < n; ++i) ans[i] = (i > 0 ? pref[i-1] : 1) * (i + 1 < n ? suff[i+1] : 1) % MOD;
return ans;
}
vector<ll> get_weights(vector<int> P, int M) {
int N = (int)P.size() - M;
vector<vector<int>> children(N + M);
for (int i = 1; i < N + M; ++i) children[P[i]].push_back(i);
vector<ll> assign_ways(N + M, 1);
for (int i = N - 1; i >= 0; --i) {
assign_ways[i] = children[i].size();
for (int ch : children[i]) assign_ways[i] = (assign_ways[i] * assign_ways[ch]) % MOD;
}
vector<ll> ans(N + M, 1);
for (int i = 0; i < N; ++i) {
vector<ll> ways_children(children[i].size());
for (int j = 0; j < children[i].size(); ++j) ways_children[j] = assign_ways[children[i][j]];
vector<ll> ways_except = product_except(ways_children);
for (int j = 0; j < children[i].size(); ++j) ans[children[i][j]] = (ans[children[i][j]] * ways_except[j] % MOD * ans[i]) % MOD;
}
return vector(begin(ans) + N, end(ans));
}
struct CircuitTree {
ll total, totalFlip;
int wt, al, ar;
bool lazy;
unique_ptr<CircuitTree> left, right;
void combine() {
total = (left->total + right->total) % MOD;
totalFlip = (left->totalFlip + right->totalFlip) % MOD;
}
void propagate() {
if (lazy) {
swap(total, totalFlip);
if (left) left->lazy = right->lazy = true;
lazy = false;
}
}
CircuitTree() {}
CircuitTree(int i, int j, const vector<ll> &weights, const vector<int> &init) : total(0), totalFlip(0), al(i), ar(j), lazy(false) {
if (i == j) {
wt = totalFlip = weights[i];
if (init[i]) swap(total, totalFlip);
} else {
int k = (i + j) / 2;
left = make_unique<CircuitTree>(i, k, weights, init);
right = make_unique<CircuitTree>(k + 1, j, weights, init);
combine();
// cerr << "[" << i << ", " << j << "] total " << total << " " << totalFlip << endl;
}
}
void flip(int i, int j) {
propagate();
if (j < al || ar < i) return;
if (i <= al && ar <= j) {
lazy = !lazy; propagate();
} else {
left->flip(i, j); right->flip(i, j);
combine();
}
}
ll sum() {
propagate();
return total;
}
};
struct DumbCircuitTree {
vector<int> p, a;
int n, m;
vector<vector<int>> children;
DumbCircuitTree() {}
DumbCircuitTree(vector<int> p, vector<int> a) : p(p), a(a), n((int)p.size() - (int)a.size()), m(a.size()), children(n + m) {
for (int i = n + m - 1; i > 0; --i) children[p[i]].push_back(i);
}
void flip(int L, int R) {
for (int j = L; j <= R; ++j) a[j] = 1 - a[j];
}
bool check_state(vector<int> &thresholds) {
vector<int> st(n + m);
for (int i = 0; i < m; ++i) st[i+n] = a[i];
for (int i = n-1; i >= 0; --i) {
int active = 0;
for (int ch : children[i]) if (st[ch] == 1) ++active;
if (active >= thresholds[i]) st[i] = 1;
}
// cerr << thresholds << " " << st << endl;
return st[0] == 1;
}
int _count_ways(vector<int> &thresholds, int i) {
if (i == n) return check_state(thresholds) ? 1 : 0;
else {
int ans = 0;
for (int ct = 1; ct <= children[i].size(); ++ct) {
thresholds[i] = ct;
ans += _count_ways(thresholds, i + 1);
}
return ans;
}
}
int count_ways() {
// cerr << "got ct " << endl;
vector<int> thresholds(n, 1);
return _count_ways(thresholds, 0);
}
};
CircuitTree ct;
DumbCircuitTree dct;
int N;
void init(int _N, int M, std::vector<int> P, std::vector<int> A) {
N = _N;
vector<ll> weights = get_weights(P, M);
ct = CircuitTree(0, M - 1, weights, A);
dct = DumbCircuitTree(P, A);
}
int count_ways(int L, int R) {
ct.flip(L - N, R - N);
// dct.flip(L - N, R - N);
return ct.sum();
// assert(ct.sum() == dct.count_ways());
// return dct.count_ways();
}
Compilation message
circuit.cpp: In function 'std::vector<long long int> get_weights(std::vector<int>, int)':
circuit.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for (int j = 0; j < children[i].size(); ++j) ways_children[j] = assign_ways[children[i][j]];
| ~~^~~~~~~~~~~~~~~~~~~~
circuit.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for (int j = 0; j < children[i].size(); ++j) ans[children[i][j]] = (ans[children[i][j]] * ways_except[j] % MOD * ans[i]) % MOD;
| ~~^~~~~~~~~~~~~~~~~~~~
circuit.cpp: In member function 'int DumbCircuitTree::_count_ways(std::vector<int>&, int)':
circuit.cpp:115:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for (int ct = 1; ct <= children[i].size(); ++ct) {
| ~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
600 KB |
5th lines differ - on the 1st token, expected: '481', found: '507' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
344 KB |
3rd lines differ - on the 1st token, expected: '133738288', found: '824438726' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
600 KB |
5th lines differ - on the 1st token, expected: '481', found: '507' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
406 ms |
8780 KB |
Output is correct |
| 2 |
Correct |
599 ms |
17216 KB |
Output is correct |
| 3 |
Correct |
587 ms |
17220 KB |
Output is correct |
| 4 |
Correct |
601 ms |
17336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
406 ms |
8780 KB |
Output is correct |
| 2 |
Correct |
599 ms |
17216 KB |
Output is correct |
| 3 |
Correct |
587 ms |
17220 KB |
Output is correct |
| 4 |
Correct |
601 ms |
17336 KB |
Output is correct |
| 5 |
Incorrect |
472 ms |
8780 KB |
3rd lines differ - on the 1st token, expected: '249436868', found: '812217068' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
344 KB |
3rd lines differ - on the 1st token, expected: '133738288', found: '824438726' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
600 KB |
5th lines differ - on the 1st token, expected: '481', found: '507' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
600 KB |
5th lines differ - on the 1st token, expected: '481', found: '507' |
| 4 |
Halted |
0 ms |
0 KB |
- |
