This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// Be name khoda //
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define debug(x) cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
const int mod = 1000002022;
const int maxn5 = 2e5 + 10;
const int maxnt = 1e6 + 10;
vector <int> adj[maxn5];
int n, m;
ll val[maxn5], all[maxn5];
void fix(int &a){
if(a >= mod)
a -= mod;
}
namespace seg{
int sum[maxnt][2];
bool lazy[maxnt];
void toggle(int l, int r, int lq, int rq, int v){
if(rq <= l || r <= lq)
return;
if(lq <= l && r <= rq){
lazy[v] ^= 1;
swap(sum[v][0], sum[v][1]);
return;
}
int mid = (l + r) >> 1;
toggle(l, mid, lq, rq, v * 2);
toggle(mid, r, lq, rq, v * 2 + 1);
fix(sum[v][0] = sum[v * 2][0] + sum[v * 2 + 1][0]);
fix(sum[v][1] = sum[v * 2][1] + sum[v * 2 + 1][1]);
if(lazy[v])
swap(sum[v][0], sum[v][1]);
return;
debug(l);
debug(r);
debug(lq);
debug(rq);
debug(sum[v][0]);
debug(sum[v][1]);
debug(lazy[v]);
debug(sum[v * 2 + 1][0]);
}
void build(int l, int r, int v){
if(r - l == 1){
sum[v][0] = 0;
sum[v][1] = val[l + n];
return;
}
int mid = (l + r) >> 1;
build(l, mid, v * 2);
build(mid, r, v * 2 + 1);
fix(sum[v][0] = sum[v * 2][0] + sum[v * 2 + 1][0]);
fix(sum[v][1] = sum[v * 2][1] + sum[v * 2 + 1][1]);
}
}
void dfs2(int v){
ll x = val[v];
for(auto u : adj[v]){
val[u] = x;
x = x * all[u] % mod;
}
x = val[v];
reverse(all(adj[v]));
for(auto u : adj[v]){
val[u] = val[u] * x % mod;
dfs2(u);
x = x * all[u] % mod;
}
return;
debug(v);
debug(all[v]);
debug(val[v]);
debug(val[6]);
}
void dfs1(int v){
all[v] = max(1, int(adj[v].size()));
for(auto u : adj[v]){
dfs1(u);
all[v] = all[v] * all[u] % mod;
}
}
void init(int N, int M, std::vector<int> p, std::vector<int> a) {
n = N;
m = M;
for(int i = 1; i < n + m; i++)
adj[p[i]].pb(i);
val[0] = 1;
dfs1(0);
dfs2(0);
seg::build(0, m, 1);
for(int i = 0; i < m; i++){
//debug(i);
//debug(val[i + n]);
if(a[i])
seg::toggle(0, m, i, i + 1, 1);
}
}
int count_ways(int l, int r) {
l -= n;
r -= n;
seg::toggle(0, m, l, r + 1, 1);
return seg::sum[1][0];
}
# | 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... |